首页 > 代码库 > HDOJ 5000 Clone
HDOJ 5000 Clone
所有满足的情况的属性和是一定的,而且属性和等于sum/2时得到的结果最大.
Clone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 574 Accepted Submission(s): 277
Problem Description
After eating food from Chernobyl, DRD got a super power: he could clone himself right now! He used this power for several times. He found out that this power was not as perfect as he wanted. For example, some of the cloned objects were tall, while some were short; some of them were fat, and some were thin.
More evidence showed that for two clones A and B, if A was no worse than B in all fields, then B could not survive. More specifically, DRD used a vector v to represent each of his clones. The vector v has n dimensions, representing a clone having N abilities. For the i-th dimension, v[i] is an integer between 0 and T[i], where 0 is the worst and T[i] is the best. For two clones A and B, whose corresponding vectors were p and q, if for 1 <= i <= N, p[i] >= q[i], then B could not survive.
Now, as DRD‘s friend, ATM wants to know how many clones can survive at most.
More evidence showed that for two clones A and B, if A was no worse than B in all fields, then B could not survive. More specifically, DRD used a vector v to represent each of his clones. The vector v has n dimensions, representing a clone having N abilities. For the i-th dimension, v[i] is an integer between 0 and T[i], where 0 is the worst and T[i] is the best. For two clones A and B, whose corresponding vectors were p and q, if for 1 <= i <= N, p[i] >= q[i], then B could not survive.
Now, as DRD‘s friend, ATM wants to know how many clones can survive at most.
Input
The first line contains an integer T, denoting the number of the test cases.
For each test case: The first line contains 1 integer N, 1 <= N <= 2000. The second line contains N integers indicating T[1], T[2], ..., T[N]. It guarantees that the sum of T[i] in each test case is no more than 2000 and 1 <= T[i].
For each test case: The first line contains 1 integer N, 1 <= N <= 2000. The second line contains N integers indicating T[1], T[2], ..., T[N]. It guarantees that the sum of T[i] in each test case is no more than 2000 and 1 <= T[i].
Output
For each test case, output an integer representing the answer MOD 10^9 + 7.
Sample Input
2 1 5 2 8 6
Sample Output
1 7
Source
2014 ACM/ICPC Asia Regional Anshan Online
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int LL; const LL mod=(1e9+7); int v[2020],n; LL sum,dp[2][2000400]; int main() { int T_T; scanf("%d",&T_T); while(T_T--) { scanf("%d",&n); sum=0; for(int i=0;i<n;i++) { scanf("%d",v+i); sum+=v[i]; } memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) { if(i==0) { for(int j=0;j<=v[i];j++) dp[0][j]=1; continue; } for(int j=0;j<=sum/2;j++) { int temp=0; for(int k=0;k<=v[i]&&k<=j;k++) { temp=(temp+dp[(i%2)^1][j-k])%mod; } dp[i%2][j]=temp; } } printf("%d\n",dp[(n-1)%2][sum/2]); } return 0; }
HDOJ 5000 Clone
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。