http://acm.hdu.edu.cn/showproblem.php?pid=1158
题意：一项工程需要n个月完成，但每个月需要的人数不一样。给出每个月需要的最少人数。已知，经理雇佣一个人，解雇一个人的花费和员工每月的工资。
3
4 5 6
10 9 11
该工程需要3个月完成，雇佣一个人花费是4,员工每月的工资是5，解雇一个人花费是6。10 9 10分别代表每个月需要的最少员工，
问完成该工程最少的成本。
思路：
num[i]表示每个月需要的最少人数，maxn表示需要的最多人数。
dp[i][j]表示第i个月雇佣j个人时，前i个月的总花费，（ num[i] <= j <= maxn）。
那么 Dp[i-1]中的每一项都可能影响到Dp[i],即使Num[i-1]<<Num[i],所以用dp[i-1]中的每一项去求dp[i]，
对于 num[i-1] <= k <= maxn，如果 k < j就雇佣，如果k > j就解雇。这样求出最小值就是dp[i][j]。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[13][110];
int num[13];
int main()
{
int n;
while(~scanf("%d",&n) && n)
{
int hiring,sal,firing;
int maxn = -1;
scanf("%d %d %d",&hiring,&sal,&firing);
for(int i = 1; i <= n; i++)
{
scanf("%d",&num[i]);
maxn = max(maxn,num[i]);
}
memset(dp,0,sizeof(dp));
for(int j = num[1]; j <= maxn; j++)
dp[1][j] = j*(hiring + sal);
int t,tmp;
for(int i = 2; i <= n; i++)
{
for(int j = num[i]; j <= maxn; j++)//求第i个月j个人时的最小花费
{
tmp = INF;
for(int k = num[i-1]; k <= maxn; k++)//根据上一个月来求，枚举上一个月的人数k，
{
if(k < j)
t = dp[i-1][k] + (j-k)*hiring + j*sal;
else if(k == j)
t= dp[i-1][k]+k*sal;
else
t = dp[i-1][k]+(k-j)*firing+j*sal;
tmp = min(tmp,t);
}
dp[i][j] = tmp;
}
}
int ans = INF;
for(int i = num[n]; i <= maxn; i++)
{
ans = min(ans,dp[n][i]);
}
printf("%d\n",ans);
}
return 0;
}
hdu 1158 Employment Planning(dp),布布扣,bubuko.com
hdu 1158 Employment Planning(dp)
原文：http://blog.csdn.net/u013081425/article/details/19979939