首页 > 代码库 > HDU 5000
HDU 5000
http://acm.hdu.edu.cn/showproblem.php?pid=5000
题意:有n种属性,每种属性的数值可以是0-T[i],当一个人属性全部小于等于另一个人的属性时,小的那个人会被淘汰,问最多同时存在多少人
比赛的时候没有想到这题的关键点,没出来也是情理之中
解法:sum表示一个人的属性和。首先,人数最多的情况下这些人的sum是相同的,因为这种情况下一个属性减少另一个属性必然增加,保证满足条件。其次发现,sum=0的方案数和sum=ΣT[i]的方案数相同,因此在sum=(ΣT[i])/2取得最大值(没找到完整的推理,只是根据猜测。。)。这样问题转化为n个数,每个数可以取0-T[i],和为(ΣT[i])/2的方案数。
dp[i][j]表示选到第i个人时,属性和为j的种数
#include <iostream>#include <cstdio>#include <cstring>using namespace std ;const int mod=1000000007 ;int T[2005],dp[2005][2005] ;int main(){ int t ; scanf("%d",&t) ; while(t--) { int n ; scanf("%d",&n) ; int sum=0 ; for(int i=0 ;i<n ;i++) { scanf("%d",&T[i]) ; sum+=T[i] ; } memset(dp,0,sizeof(dp)) ; for(int i=0 ;i<=T[0] ;i++) dp[0][i]=1 ; sum>>=1 ; for(int i=1 ;i<n ;i++) { for(int j=0 ;j<=sum ;j++) { for(int k=0 ;k<=T[i] ;k++) { if(j<k)break ; dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod ; } } } printf("%d\n",dp[n-1][sum]) ; } return 0 ;}
HDU 5000
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。