DP. 用f[i][j]表示前i个月末人数为j时的最小开支.则f[i][j]=min{f[i-1][k]+cost(i,j)},其中k表示第i-1个月的人数,cost(i,j)为第i个月的开支.当k<=j时,cost(i,j)=hire*(j-k)+j*salary;当k>j时,cost(i,j)=fire*(k-j)+j*salary.详细见代码:
#include<iostream>
using namespace std;
const int inf=100000000;
int hire,fire,sal;
int mon,men[13];
int f[13][10000];
int main()
{
while(scanf("%d",&mon)!=EOF&&mon)
{
scanf("%d%d%d",&hire,&sal,&fire);
int i,j,k,MAX_NUM=0;
for(i=1;i<=mon;i++)
{
scanf("%d",&men[i]);
if(MAX_NUM<men[i]) MAX_NUM=men[i];
}
for(i=men[1];i<=MAX_NUM;i++)
f[1][i]=hire*i+sal*i;
for(i=2;i<=mon;i++)
for(j=men[i];j<=MAX_NUM;j++)
{
int minn=inf;
for(k=men[i-1];k<=MAX_NUM;k++)
{
if(k<=j&&minn>f[i-1][k]+hire*(j-k)+j*sal)
minn=f[i-1][k]+hire*(j-k)+j*sal;
else if(k>j&&minn>f[i-1][k]+fire*(k-j)+j*sal)
minn=f[i-1][k]+fire*(k-j)+j*sal;
}
f[i][j]=minn;
}
int ans=inf;
for(i=men[mon];i<=MAX_NUM;i++)
if(f[mon][i]!=0&&f[mon][i]<ans)
ans=f[mon][i];
printf("%d\n",ans);
}
return 0;
}
posted on 2010-08-18 21:35
wuxu 阅读(336)
评论(0) 编辑 收藏 引用 所属分类:
动态规划