首页 > 代码库 > 【USACO 2.2】Subset Sums (DP)
【USACO 2.2】Subset Sums (DP)
N (1 <= N <= 39),问有多少种把1到N划分为两个集合的方法使得两个集合的和相等。
如果总和为奇数，那么就是0种划分方案。否则用dp做。
dp[i][j]表示前 i 个数划分到一个集合里，和为j的方法数。
dp[i][j]=dp[i-1][j]+dp[i][j-i]
n 为 39 时，1 到 39 的和为 780，枚举 j 的时候枚举到 s/2，最后输出dp[n][s/2]/2。
http://train.usaco.org/usacoprob2?a=z5hb7MFUmsX&S=subset
/*TASK: subsetLANG: C++*/#include<bits/stdc++.h>int n;int s,ans;long long dp[100][1000];int main(){ freopen("subset.in","r",stdin); freopen("subset.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)s+=i; dp[0][0]=1; if(s%2==0) for(int i=1;i<=n;i++){ for(int j=0;j<=s/2;j++) dp[i][j]+=dp[i-1][j]+(j>=i?dp[i-1][j-i]:0); printf("%lld\n",dp[n][s/2]/2);}
【USACO 2.2】Subset Sums (DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。