这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1158
不知道为啥，这道DP把我脑袋快转晕了，有个地方想到了，可就是转不过去，真晕菜。
不过历经2小时，还是写出来了，这花的时间，真囧。。。。
分析：
DP，这一题数据范围没给出，不严谨。经测试，公认数量开105就行了，工资我现开始开0xffff，然后WA了，接着开了0x3ffffff，就AC了。
数组dp[i][j]表示第i个月员工数为j的总花费。
这题逐层(月)考虑，在上一层顺序遍历每一个dp[i-1][j] != INF的：
1.如果上一层(月)(即j)比本层(月)要求的人数(即man[i])少，则只需要雇佣相差的人数
2.如果上一层比本层要求人数多，则在man[i]和j之间，dp各个情况就行。
说不清楚~~具体看代码：
/* Tanky Woo
* HDU 1158 DP
* 2012.2.2
*/
#include <iostream>
using namespace std;
int mo;
int hire, salary, fire;
int man[15];
int dp[15][105];
const int INF = 0x3ffffff;
int SML(int a, int b)
{
return a<b? a:b;
}
int main()
{
while(cin >> mo && mo)
{
cin >> hire >> salary >> fire;
int _min=INF, _max=0;
for(int i=1; i<=mo; ++i)
{
cin >> man[i];
if(man[i]>_max) _max = man[i];
if(man[i]<_min) _min = man[i];
}
//memset(dp, 0, sizeof(dp));
for(int i=1; i<=mo; ++i)
for(int j=0; j<=105; ++j)
dp[i][j] = INF;
dp[1][man[1]] = man[1]*(hire + salary);
for(int i=2; i<=mo; ++i)
{
for(int j=_min; j<=_max; ++j)
{
if(dp[i-1][j] == INF)
continue;
if(man[i] >= j)
dp[i][man[i]] = SML(dp[i][man[i]], dp[i-1][j]+hire*(man[i]-j)+salary*man[i]);
else
for(int k=man[i]; k<=j; ++k)
dp[i][k] = SML(dp[i][k], dp[i-1][j]+fire*(j-k)+salary*k);
}
}
int imin = INF;
for(int i=_min; i<=_max; ++i)
if(imin > dp[mo][i])
imin = dp[mo][i];
cout << imin << endl;
}
return 0;
}