0-1背包模型,每个人的决策为装 0-j 个storage,j为当前剩余storage的数量
先求出最大的L,再用这个L重新做一次dp,找出最小的Y
Run Time: 0.016s
#define UVa "9-9.10163.cpp" //Storage Keepers char fileIn[30] = UVa, fileOut[30] = UVa; #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<iostream> using namespace std; //Global Variables. Reset upon Each Case! const int maxm = 30 + 5, maxn = 100 + 5, INF = 1<<30; int n, m, p[maxm]; int d[maxn][maxn]; int d2[maxn][maxn]; int maxL; ///// int main() { while(scanf("%d%d", &n, &m) && n) { for(int i = 0; i < m; i ++) scanf("%d", &p[i]); for(int i = m-1; i >= 0; i --) { for(int j = 0; j <= n; j ++) { int& u = d[i][j]; if(j == 0) { u = INF; } else { if(i == m-1) { u = p[i]/j; } else { u = d[i+1][j]; for(int k = 1; k <= j; k ++) { u = max(u, min(p[i]/k, d[i+1][j-k])); } } } } } maxL = d[0][n]; for(int i = m-1; i >= 0; i --) { for(int j = 0; j <= n; j ++) { int& u = d2[i][j]; u = INF; if(j == 0) { u = 0; } else { if(i == m-1) { if(p[i]/j >= maxL) { u = p[i]; //else u = INF } } else { if(d[i+1][j] >= maxL) { u = d2[i+1][j]; } for(int k = 1; k <= j; k ++) { if(min(p[i]/k, d[i+1][j-k]) >= maxL) { u = min(u, d2[i+1][j-k] + p[i]); } } } } } } if(!maxL) d2[0][n] = 0; printf("%d %d\n", d[0][n], d2[0][n]); } return 0; }