HDU 1158 Employment Planning （DP)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
using namespace std;
int h,w,f;
int a[100000];
;int dp[15][100000];
int main()
{
    int n,maxn,minn;
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d%d%d",&h,&w,&f);
        int maxn=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>maxn)
                maxn=a[i];
        }
        for(int j=a[1];j<=maxn;j++)//第一天的状态可以确定
            dp[1][j]=(h+w)*j;
        for(int i=2;i<=n;i++)
        {
            for(int j=a[i];j<=maxn;j++)//j天雇佣的人数
            {
                minn=INT_MAX;
                for(int k=a[i-1];k<=maxn;k++)//j的前一天雇佣人数
                {
                    if(j>=k)
                        dp[i][j]=(j-k)*h+j*w+dp[i-1][k];
                    else
                        dp[i][j]=(k-j)*f+j*w+dp[i-1][k];
                    if(dp[i][j]<minn)
                        minn=dp[i][j];
                }
                dp[i][j]=minn;//取最小值
            }
        }
        minn=INT_MAX;
        for(int i=a[n];i<=maxn;i++)//不确定最后一天雇佣了几个人，所以要遍历
        {
            if(dp[n][i]<minn)
                minn=dp[n][i];
        }
        printf("%d\n",minn);
    }
    return 0;
}