[UVA][dp] 882 - The Mailbox Manufacturers Problem＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-06-28 10:28:45| 人1,960| 回1 | 上一篇 | 下一篇

[UVA][dp] 882 - The Mailbox Manufacturers Problem

推 0 收藏 0 0 站台

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

1 10

1 100

3 73

5 100

Output for sample input

5050

382

495

目描述：
在有 k 箱(?)，每箱共同有一最低下限的炸可以被引爆，在已知道一次最多放 m 炸，在只能使用 k 箱行找到最低下限，最小的炸量是多少。

目解法：
使用 dp[i][j][k] 在只剩下 i 箱可以, 已知道炸介於 j ~ k。
下次使用的炸量, 因此分成炸掉或者炸掉, 者取最大使用量的。

#include <stdio.h>
#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;
}