所有满足的情况的属性和是一定的,而且属性和等于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
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.
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;
}