[UVA][dp] 882 - The Mailbox Manufacturers Problem
The Mailbox Manufacturers Problem
In the good old days when Swedish children were still allowed to blow up their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k (1<= k<=10) identical mailbox prototypes each fitting up to m (1<=m<=100) crackers. However, he is not sure of how many fire-crackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say: ”Well, if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up even when filled with m crackers, I would need 1 + 2 + 3 + ... + m = m * (m + 1)/2 crackers. If m = 100 that would mean more than 5000 fire-crackers!”. ”That’s too many”, he replies. ”What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?”
Can you? And what is the minimum number of crackers that you should ask him to provide you with?
You may assume the following:
1. If a mailbox can withstand x fire-crackers, it can also withstand x-1 fire-crackers.
2. Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.
Note: If the mailbox can withstand a full load of m fire-crackers, then the manufacturer will of course be satisfied with that answer. But otherwise he is looking for the maximum number of crackers that his mailboxes can withstand.
Input specifications
The input starts with a single integer N(1<=N<=10) indicating the number of test cases to follow. Each test case is described by a line containing two integers: k and m, separated by a single space.
Output specifications
For each test case print one line with a single integer indicating the minimum number of fire-crackers that is needed, in the worst case, in order to figure out how many crackers the mailbox prototype can withstand.
Sample input
4
1 10
1 100
3 73
5 100
Output for sample input
55
5050
382
495
題目描述：
現在有 k 個郵箱(?)，每個郵箱共同有一個最低下限的炸藥數可以被引爆，現在已經知道一次最多放 m 個炸藥，問在只能使用 k 個郵箱進行測試找到最低下限時，最小的炸藥總量是多少個。
題目解法：
使用動態規劃 dp[i][j][k] 在只剩下 i 個郵箱可以測試時, 已經知道炸藥範圍介於 j ~ k。
窮舉下次使用的炸藥量, 因此會分成炸掉或者沒炸掉, 兩者取最大使用量的狀態。
#include <string.h>
#include <algorithm>
using namespace std;
int dp[15][105][105];
int used[15][105][105];
#define oo 0xfffffff
int dfs(int k, int l, int r) {
if(l == r) return 0;
if(k == 0) return oo;
if(used[k][l][r])
return dp[k][l][r];
used[k][l][r] = 1;
int i;
int &ret = dp[k][l][r];
ret = oo;
for(i = l+1; i <= r; i++)
ret = min(ret, i+max(dfs(k-1, l, i-1),dfs(k, i, r)));
return ret;
}
int main() {
memset(used, 0, sizeof(used));
int testcase, k, m;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &k, &m);
printf("%d\n", dfs(k, 0, m));
}
return 0;
}
請問可以講解一下嗎?>////<
我不太懂