HDU 1158 传送门:Employment Planning
题目大意：
一个项目经理准备招一部分工人做事，每个月所需要的工人人数不一样，
经理可以看情况hires or fires a worker,雇人或解雇都需要钱，雇的人不干活也需要发工资，
要求怎样安排才能使得完成整个工作花费最少?
分析 :
以第i个月结束时，现有j个人的最小花费dp[i][j]为状态量，对人数进行举,
状态转移方程 : dp[i][j] = min(dp[i][j] , dp[i][k] + cost ,( num[i-1]< k < max))
Code:
#include"stdio.h"
#define MAX_WORKER 0x9999
int months;
int hireCost, salary, fireCost;
int minMonthWorker[13],maxWorker; //每个月份雇佣的最小人数
int cost[13][MAX_WORKER]; // 月份 & 工人数
void input();
void initCostArray();
void calculateCostArray();
void out();
int main(){
while(~scanf("%d",&months),months)
{
input();
out();
}
return 0;
}
void input(){
scanf("%d%d%d",&hireCost,&salary,&fireCost);
maxWorker = 0;
for(int i = 1;i <= months;i ++){
scanf("%d",&minMonthWorker[i]);
if(minMonthWorker[i] > maxWorker) {
maxWorker = minMonthWorker[i];
}
}
initCostArray();
}
void initCostArray(){
for(int i = minMonthWorker[1];i <= maxWorker;i ++){
cost[1][i] = hireCost*i + salary*i;
}
calculateCostArray();
}
void calculateCostArray(){
for(int i = 2; i <= months; i ++){
for(int j = minMonthWorker[i]; j <= maxWorker; j ++){
int costMin = 0x999999;
int temp;
for(int k = minMonthWorker[i-1]; k <= maxWorker ;k ++){
if(k > j){
temp = cost[i-1][k] + fireCost*(k-j) + salary*j;
}else{
temp = cost[i-1][k] + hireCost*(j-k) + salary*j;
}
if(temp < costMin)
costMin = temp;
}
cost[i][j] = costMin;
}
}
}
void out(){
int tempMin = 0x999999;
for(int i = minMonthWorker[months] ; i <= maxWorker; i ++)
if(cost[months][i] < tempMin)
tempMin = cost[months][i];
printf("%d\n",tempMin);
}