hdu 1158 Employment Planning

题意：

一个项目需要n个月完成，hire一个人所需的费用、每个人一个月的工资、fire一个人所需的费用。

以及每个月至少要雇佣xi个人。

求完成项目所需要的最少投入资金。

分析：

状态转移方程：dp[i][j]=min(dp[i-1][k]+j*s+k>l?(k-j)*fire:(j-k)*hire)    p[i-1]<=k<=maxp

dp[i][j]表示到i月为止，第i月雇佣j个人所需要的资金。

(i表示月,j表示人数）

p[i]表示第i个月需要的最少人数,maxp是所需的最大人数。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[13][1010];
int p[1010];

int main()
{
    int n,hire,salary,fire,ans,maxp;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        scanf("%d%d%d",&hire,&salary,&fire);
        maxp=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
            if(p[i]>maxp)
                maxp=p[i];
        }
        memset(dp,0x3f,sizeof(dp));
        for(int i=p[1];i<=maxp;i++)
            dp[1][i]=i*(hire+salary);
        for(int i=2;i<=n;i++)
        {
            for(int j=p[i];j<=maxp;j++)
            {
                if(p[i-1]<j)
                    dp[i][j]=min(dp[i][j],dp[i-1][p[i-1]]+salary*j+(j-p[i-1])*hire);
                else
                    dp[i][j]=min(dp[i][j],dp[i-1][p[i-1]]+salary*j+(p[i-1]-j)*fire);
                for(int k=p[i-1];k<=maxp;k++)
                {
                    if(k>j)
                        dp[i][j]=min(dp[i][j],dp[i-1][k]+salary*j+(k-j)*fire);
                    else
                        dp[i][j]=min(dp[i][j],dp[i-1][k]+salary*j+(j-k)*hire);
                }
            }
        }
        ans=10000000;
        for(int i=p[n];i<=maxp;i++)
        {
            if(ans>dp[n][i])
                ans=dp[n][i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu 1158 Employment Planning

原文：http://blog.csdn.net/u012841845/article/details/18620557