[UVA][dp] 10163 - Storage Keepers
Problem C.Storage Keepers
| Problem C.Storage Keepers |
Background
Randy Company has N (1<=N<=100) storages. Company wants some men to keep them safe. Now there are M (1<=M<=30) men asking for the job. Company will choose several from them. Randy Company employs men following these rules:
1. Each keeper has a number Pi (1<=Pi<=1000) , which stands for their ability.
2. All storages are the same as each other.
3. A storage can only be lookd after by one keeper. But a keeper can look after several storages. If a keeper’s ability number is Pi, and he looks after K storages, each storage that he looks after has a safe number Uj=Pi div K.(Note: Uj, Pi and K are all integers). The storage which is looked after by nobody will get a number 0.
4. If all the storages is at least given to a man, company will get a safe line L=min Uj
5. Every month Randy Company will give each employed keeper a wage according to his ability number. That means, if a keeper’s ability number is Pi, he will get Pi dollars every month. The total money company will pay the keepers every month is Y dollars.
Now Randy Company gives you a list that contains all information about N,M,P, your task is give company a best choice of the keepers to make the company pay the least money under the condition that the safe line L is the highest.
Input
The input file contains several scenarios. Each of them consists of 2 lines:
The first line consists of two numbers (N and M), the second line consists of M numbers, meaning Pi (I=1..M). There is only one space between two border numbers.
The input file is ended with N=0 and M=0.
Output
For each scenario, print a line containing two numbers L(max) and Y(min). There should be a space between them.
Sample Input
2 1
7
1 2
10 9
2 5
10 8 6 4 1
5 4
1 1 1 1
0 0
Sample Output
3 7
10 10
8 18
0 0
題目描述：
有 n 個倉庫和 m 個工人，每個工人都有其能力，雇用的費用等於能力高低。
而倘若一個工人去顧多個倉庫，則倉庫安全度為該工人能力除以顧的倉庫個數取整。
而 n 個倉庫的整體安全度為所有倉庫安全度的最小值。
求在最高安全度下，花費最少為何？
題目解法：
dp[i][j] 表示考慮第 i 個工人時，此時已經分配 j 個倉庫被管理的最高安全度。
由於要求最少花費，因此要額外多做一次，同時進行會造成多餘的花費，
因為中途不見得一定要最高安全度的轉移。
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
int n, m;
int dp1[105][105], dp2[105][105], p[105];
int i, j, k;
while(scanf("%d %d", &n, &m) == 2 && n) {
for(i = 0; i < m; i++)
scanf("%d", &p[i]);
memset(dp1, 0, sizeof(dp1));
memset(dp2, 63, sizeof(dp2));
for(i = 0; i < m; i++) {
dp1[i][0] = 0xfffffff;
for(j = 0; j <= n; j++) {
dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j]);
for(k = 1; j+k <= n; k++) {
int val = min(dp1[i][j], p[i]/k);
dp1[i+1][j+k] = max(dp1[i+1][j+k], val);
}
}
}
int mx = dp1[m][n];
for(i = 0; i < m; i++) {
dp2[i][0] = 0;
for(j = 0; j <= n; j++) {
if(dp1[i+1][j] >= mx)
dp2[i+1][j] = min(dp2[i+1][j], dp2[i][j]);
for(k = 1; j+k <= n; k++) {
int val = min(dp1[i][j], p[i]/k);
if(val >= mx)
dp2[i+1][j+k] = min(dp2[i+1][j+k], dp2[i][j]+p[i]);
}
}
}
if(mx == 0) dp2[m][n] = 0;
printf("%d %d\n", mx, dp2[m][n]);
}
return 0;
}