题目传送门
【题目大意】
要连续进行$n$个月的工作，第$i$个月最少需要$num_i$个工人，雇佣和解雇工人都需要固定的费用$h$和$f$，且工人在雇佣状态无论有没有工作都要支付工资$c$，求最少需要多少费用。
【思路分析】
显然是一道DP的题目啦！设$dp[i][j]$表示在第$i$个月有$j$个工人所需要的总费用，转移时考虑是否多雇佣人或解雇人，分情况讨论。
对于$dp[i-1][k]$：
1.若$j\le k$，即解雇了多余的工人
$$dp[i][j]=min(dp[i][j],dp[i-1][k]+j*c+(k-j)*f)$$
2.若$j>k$，即雇佣了多余的工人
$$dp[i][j]=min(dp[i][j],dp[i-1][k]+j*c+(j-k)*h)$$
初始值：$dp[1][i]=i*(h+c)$，其余为$+\infty$
答案：$max\{dp[n][i]\}(i\in[num_n,max\{num\}])$
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define g() getchar() 7 #define rg register 8 #define go(i,a,b) for(rg int i=a;i<=b;i++) 9 #define back(i,a,b) for(rg int i=a;i>=b;i--) 10 #define db double 11 #define ll long long 12 #define il inline 13 #define pf printf 14 using namespace std; 15 int fr(){ 16 int w=0,q=1; 17 char ch=g(); 18 while(ch<'0'||ch>'9'){ 19 if(ch=='-') q=-1; 20 ch=g(); 21 } 22 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 23 return w*q; 24 } 25 int n,a,b,c,dp[15][10002],num[15]; 26 const int INF=1e9+7; 27 int main(){ 28 //freopen("","r",stdin); 29 //freopen("","w",stdout); 30 n=fr(); 31 while(n){ 32 a=fr();b=fr();c=fr(); 33 rg int maxn=0; 34 go(i,1,n) num[i]=fr(),maxn=max(maxn,num[i]); 35 go(i,1,maxn) dp[1][i]=i*(a+b); 36 go(i,2,n) go(j,num[i],maxn){ 37 dp[i][j]=INF; 38 go(k,num[i-1],maxn){ 39 rg int add=j*b; 40 if(j<k) add+=(k-j)*c; 41 else add+=(j-k)*a; 42 dp[i][j]=min(dp[i][j],dp[i-1][k]+add); 43 } 44 } 45 rg int ans=INF; 46 go(i,num[n],maxn) ans=min(ans,dp[n][i]); 47 pf("%d\n",ans); 48 n=fr(); 49 } 50 return 0; 51 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11390619.html
