UVA 10163 二次DP

题意

n个仓库，m个人应聘，第i个应聘者能力为p[i]。一个人可以守卫多个仓库，但一个仓库最多只能有一个人守卫。能力p[i]的应聘者工资为p[i]，当一个人守卫多个仓库时，该仓库的防御值为p[i]/仓库个数。求最低防御值最大的情况下，工资总和最小是多少？

题解

首先求最低防御值的最大值。设dp[i][j]为i个人守j个仓库时的最大防御值，则dp[i][j]=max(dp[i][j],min(dp[i-1][j-k],p[i]/k))（0 < k <=j）。然后求最小工资总和，设sp[i][j]为i个人守j个仓库时的最小工资总和，p[i]/k>=dp[m][n]时（即守卫分散到每个仓库的防御值大于最低防御值时），sp[i][j]=min(sp[i][j],sp[i-1][j-k]+p[i])。

注意事项

注意初始化问题。dp[0][0]要初始化为INF，因为dp[0][0]会影响dp[i-1][j-k]的取值。整个sp数组也要初始化为INF。

代码

#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #define INF 1e9 using namespace std; int p[40]; int dp[40][120]; int sp[40][120]; int main() { int n,m; while(scanf("%d%d",&n,&m)){ if(n+m==0) break; for(int i=1;i<=m;i++){ scanf("%d",&p[i]); } memset(dp,0,sizeof(dp)); dp[0][0]=INF; for(int i=1;i<=m;i++){ dp[i][0]=INF; for(int j=1;j<=n;j++){ dp[i][j]=dp[i-1][j]; for(int k=1;k<=j;k++){ dp[i][j]=max(dp[i][j],min(dp[i-1][j-k],p[i]/k)); } } } for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ sp[i][j]=INF; } } for(int i=1;i<=m;i++){ sp[i-1][0]=0; for(int j=1;j<=n;j++){ sp[i][j]=sp[i-1][j]; for(int k=1;k<=j;k++){ int s=p[i]/k; if(s>=dp[m][n]){ sp[i][j]=min(sp[i][j],sp[i-1][j-k]+p[i]); } } } } printf("%d %d\n",dp[m][n],dp[m][n]==0?0:sp[m][n]); } return 0; }