题意:有(n(n<=12))个月份的工作需要安排,第i个月至少要雇佣(Need[i])个工人.给定雇佣一个工人的雇佣费a,每个月的工资b,解雇费用c.求最少费用.
分析:设(f[i][j])表示第i个月雇佣了j名工人的最少费用,设第(i-1)个月雇佣了k名工人,
如果(j<k,f[i][j]=min(f[i][j],f[i-1][k]+b*j+c*(k-j)))
如果(j=k,f[i][j]=min(f[i][j],f[i-1][k]+b*j))
如果(j>k,f[i][j]=min(f[i][j],f[i-1][k]+a*(j-k)+b*j))
初始化(f[0][0]=0),其余赋值无穷大.
枚举的时候,第i个月至少需要(Need[i])个工人,这是下界;然后雇佣的工人数量不应该超过(maxn(maxn=max_{Need[i]})),这是上界.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int Need[15],f[15][10005];
int main(){
while(1){
int n=read();if(!n)break;
int a=read(),b=read(),c=read(),maxn=0;
for(int i=1;i<=n;++i)Need[i]=read(),maxn=max(maxn,Need[i]);
memset(f,0x3f,sizeof(f));f[0][0]=0;
for(int i=1;i<=n;++i)
for(int j=Need[i];j<=maxn;++j)
for(int k=Need[i-1];k<=maxn;++k){
if(j<k)f[i][j]=min(f[i][j],f[i-1][k]+b*j+c*(k-j));
else if(j==k)f[i][j]=min(f[i][j],f[i-1][k]+b*j);
else if(j>k)f[i][j]=min(f[i][j],f[i-1][k]+a*(j-k)+b*j);
}
int ans=1e9;
for(int i=Need[n];i<=maxn;++i)ans=min(ans,f[n][i]);
printf("%d
",ans);
}
return 0;
}