HDU 5000 2014 ACM/ICPC Asia Regional Anshan Online DP
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 ;
}
代码
最新文章
- tomcat配置https
- 在Angular1.X中使用CSS Modules
- jQuery Filterizr 筛选过滤
- 解决android 启动白屏问题
- 地图源改变之后mxd文件打开很慢的问题
- outlook2010怎么老提示IMAP服务器已关闭连接啊
- apply和call详解
- 转:修改类不重启tomcat 自动加载项目
- hdu 4512 吉哥系列故事——完美队形I LCIS
- R与数据分析旧笔记(一)基本数学函数的使用
- java写文件时,输出不完整的原因以及解决方法close()或flush()
- 网络协议学习(2)---IP地址
- JQuery加载html网页
- my soft
- springboot系列十五、springboot集成PageHelper
- adb shell模拟点击事件(input tap)
- spark sql中进行sechema合并
- TFS支持移动设备,微软已经走出了第一步(手机上更新、查询工作项)
- 排序算法之快速排序Java实现
- jq 抖动效果