Hdu 1158 Employment Planning(DP)

#include <iostream>

#include <cstring>

#include <cstdio>



using namespace std;



const int MAXN = 100 + 28;

int dp[15][MAXN];

int workers[15];



inline int Min( int a, int b )

{

    return a<b ? a : b;

}



int main()

{

    int N;

    int hire, salary, fire;

    int maxC;

    int i, j, k;

    int minC;

    while( scanf("%d",&N)!=EOF && N )

    {

        scanf("%d%d%d", &hire, &salary, &fire);

        maxC = -1;

        for( i=1;i<=N;i++ )

        {

            scanf("%d",&workers[i]);

            maxC = maxC<workers[i] ? workers[i] : maxC;

        }

        for( i=workers[1];i<=maxC;i++ )

            dp[1][i] = hire*i + salary*i;

        for( i=2;i<=N;i++ )

        {

            for( j=workers[i];j<=maxC;j++ )

            {

                //                              

                minC = 65552365;

                for( k=workers[i-1];k<=maxC;k++ )

                {

                    if( j>k )

                        minC = Min( minC, dp[i-1][k]+(j-k)*hire+j*salary );

                    else if( k>=j )

                        minC = Min( minC, dp[i-1][k]+(k-j)*fire+j*salary );

                }

                dp[i][j] = minC;

            }

        }

        minC = 65523365;

        for( i=workers[N];i<=maxC;i++ )

            minC = Min( minC, dp[N][i] );

        printf("%d
", minC);

    }

    return 0;

}