Himalaya

#include <cstdio>
#define Nmax 501
#define INF 1000000000
using namespace std;
int N,K,C1,C2,H[Nmax],dp[Nmax][Nmax],Tata[Nmax][Nmax],sol[Nmax];

int Cost(int k,int j,int i)
{
    if(j==0)
        return 0;
    if(H[j]<=H[i])
        return dp[k][j]+(H[i]-H[j])*C1;
    else
        return dp[k][j]+(H[j]-H[i])*C2;
}

int main()
{
    freopen("himalaya.in","r",stdin);
    scanf("%d%d%d%d",&N,&K,&C1,&C2);
    for(int i=1;i<=N;++i)
        scanf("%d",&H[i]);
    for(int i=1;i<=K;++i)
        for(int j=1;j<=N;++j)
            dp[i][j]=-INF;
    dp[1][1]=0;
    for(int k=2;k<=K;++k)
        for(int i=k;i<=N;++i)
        {
            int index=k-1;
            for(int j=k-1;j<i;++j)
                if(Cost(k-1,j,i)>Cost(k-1,index,i))
                    index=j;
            dp[k][i]=Cost(k-1,index,i);
            Tata[k][i]=index;
        }
    int L=0;
    int curent=N;
    for(;K;--K)
        sol[++L]=curent,curent=Tata[K][curent];
    freopen("himalaya.out","w",stdout);
    for(int i=L;i>=1;--i)
        printf("%d ",sol[i]);
    printf("\n");
    return 0;
}