题目：http://acm.hdu.edu.cn/showproblem.php?pid=1158
这题又是看了题解，题意是一项工作需要n个月完成，雇佣一个人需要m1的钱，一个人的月工资为sa,辞退一个人需要花费m2的钱，然后给出n的数字，
代表每月需要的最少员工，问如何进行人员调整使最终花费的钱最少。
我已开始就推错了状态转移方程，因为给出的是最少的员工，所以要从当前最少员工~最多员工枚举。
还有每次需要比较num[i-1]与num[i]的大小，具体实现请看代码。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,dp[13][110];
int m1,sa,m2,num[13],maxx;
int main()
{
while(scanf("%d",&n)!=EOF&&n!=0)
{
scanf("%d%d%d",&m1,&sa,&m2);
maxx=-inf;
for(int i=1; i<=n; i++)
{
scanf("%d",&num[i]);
maxx=max(maxx,num[i]);
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=maxx;j++)
dp[i][j]=inf;
}
for(int i=1;i<=maxx;i++)
{
dp[1][i]=i*m1+i*sa;
//printf("dp[1][%d]==%d\n",i,dp[1][i]);
}
for(int i=2;i<=n;i++)
{
for(int j=num[i];j<=maxx;j++)
{
for(int k=num[i-1];k<=maxx;k++)
{
if(k>=j)
dp[i][j]=min(dp[i][j],dp[i-1][k]+(k-j)*m2+j*sa);
else
dp[i][j]=min(dp[i][j],dp[i-1][k]+(j-k)*m1+j*sa);
}
//printf("dp[%d][%d]==%d\n",i,j,dp[i][j]);
}
}
int minx=inf;
for(int i=num[n];i<=maxx;i++)
minx=min(minx,dp[n][i]);
printf("%d\n",minx);
}
return 0;
}
HDU1158：Employment Planning（线性dp)
原文：http://www.cnblogs.com/zhangmingcheng/p/4381405.html