Clone
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 8 Accepted Submission(s) : 5
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
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
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
Sample Input
2
1
5
2
8 6
Sample Output
1
7
Source
可以发现sum = 0 和 sum = 求和的方案数是一样的。
同理sum其实是对称的,和组合数一样。所以dp[n][sum / 2] 是最大的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std ;
typedef long long ll;
#define mod 1000000007
#define inf 100000
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//******************************************************************
int T,n,a[];
int dp[][];
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d",&n);
int sum=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
memset(dp,,sizeof(dp));
for(int i=;i<=a[];i++)
{
dp[][i]=;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=sum;j++)
{
for(int k=;k<=a[i]&&j+k<=sum;k++)
{
dp[i][j+k]=(dp[i][j+k]+dp[i-][j])%mod;
}
}
}
cout<<dp[n][sum/]<<endl;
}
return ;
}
代码