大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
所有的属性,以满足一定的条件,是,财产和等于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
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.
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].
2 1 5 2 8 6
1 7
#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; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117495.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...