poj 2904 The Mailboxes Manufacturers Problem(DP)
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 947
Accepted: 685
Description
In the good old days when Swedish children were still allowed to blowup 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 withk (1 ≤ k ≤ 10) identical mailbox prototypes each fitting up to m (1 ≤m ≤ 100) crackers. However, he is not sure of how many firecrackers 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. Ifm = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more thank = 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:
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
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 andm, separated by a single space.
Output
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
Sample Output
55
5050
382
495
: k , m。 m, 。 , , , 。 , 1 m , , 。 1 , t>=1 , , 。
: , 1+2+3+...+m, 。 , 。 dp[k][i][j] k , [i,j] 。
k , t , :
(1) , [i,t-1], dp[k-1][i][t-1];
(2) , [t+1,j], dp[k][t+1][j]. ( , )
, , , t, 。
AC :
#include
#include #include #include #include #include #include #include #include #define max2(a,b) ((a) > (b) ? (a) : (b)) #define min2(a,b) ((a) < (b) ? (a) : (b)) using namespace std; const int INF=10000000; int main() { int dp[15][105][105]; for(int i=1;i<=100;i++) for(int j=i;j<=100;j++) dp[1][i][j]=(j-i+1)*(i+j)/2; for(int k=2;k<=10;k++) for(int j=100;j>=1;j--) for(int i=j;i>=1;i--) { dp[k][i][j]=INF; for(int t=i;t<=j;t++) dp[k][i][j]=min(dp[k][i][j],t+max(dp[k-1][i][t-1],dp[k][t+1][j])); } int k,m,t; scanf("%d",&t); while(t--) { scanf("%d%d",&k,&m); printf("%d
",dp[k][1][m]); } return 0; }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.