Employment Planning

3 
4 5 6
10 9 11
0

199

简单dp，主要没有给出最大雇佣员工数目，当做200足够了。然后，找出当前月雇佣员工和上个月雇佣员工转化关系就好了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
#define N 15
#define M 200
#define ll __int64
const int inf=0x7fffffff;
int a[N],mmax,n;
int dp[N][M];
void inti()       
{
    int i,j;
    for(i=0;i<=n;i++)
        for(j=0;j<=mmax;j++)
        dp[i][j]=inf;
}
int main()
{
    int i,j,k,add,sal,fire;
    while(scanf("%d",&n),n)
    {
        scanf("%d%d%d",&add,&sal,&fire);
        for(i=1,mmax=0;i<=n;i++)
        {
            scanf("%d",&a[i]);
            mmax=max(mmax,a[i]);
        }
        inti();
        for(i=a[1];i<=mmax;i++)
            dp[1][i]=(add+sal)*i;
        for(i=2;i<=n;i++)
        {
            for(j=a[i-1];j<=mmax;j++) //上个月合法雇人数目
            {
                for(k=a[i];k<=mmax;k++)  //这个月合法雇人数目
                {
                    if(k<j)
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+(j-k)*fire+k*sal);
                    else
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+(k-j)*add+k*sal);
                }
            }
        }
        int ans=inf;
        for(i=a[n];i<=mmax;i++)
            ans=min(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

hdu 1158 Employment Planning

原文：http://blog.csdn.net/u011721440/article/details/44672509