USACO-Section2.2 Subset Sums

2017-9-1

题目描述

将1到n总共n个数分成两个数总和相同的集合，求出所有的种数

解答

一看到直接深搜，共2^n次方，剪枝只到36就超时了，最后用动归

代码

/* ID: 18795871 PROG: subset LANG: C++ */ #include<iostream> #include<fstream> #include<cstring> using namespace std; const int N = 800;ifstream fin("subset.in"); ofstream fout("subset.out");long dp[N+1][N+1];int main(){int i,j,n;int sum;fin>>n;sum=(n)*(n+1)/2;if (n==1||n==2||sum%2!=0){fout<<"0"<<endl;return 0;}sum/=2;dp[0][0]=1;for (i=1;i<=n;i++){for (j=1;j<=sum;j++){dp[i][j]=dp[i-1][j-i]+dp[i-1][j];}}fout<<dp[n][sum]<<endl;return 0; }

一开始写的超时代码

/* ID: 18795871 PROG: subset LANG: C++ */ #include<iostream> #include<fstream> #include<cstring> using namespace std;ifstream fin("subset.in"); ofstream fout("subset.out");int n; long cnt=0; int sum;void dfs(int m,long s1,long s2){if (m<=0) return ;if (s1+m*(m+1)/2<sum/2||s2+m*(m+1)/2<sum/2) return ;if (s1==sum/2||s2==sum/2){cnt++;return ;}if (s1+m<=sum/2) dfs(m-1,s1+m,s2);if (s2+m<=sum/2)dfs(m-1,s1,s2+m);return ; }int main(){fin>>n;sum=(n)*(n+1)/2;if (n==1||n==2||sum%2!=0){fout<<"0"<<endl;return 0;}dfs(n,0,0);fout<<cnt/2<<endl;return 0; } 新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！

总结

以上是生活随笔为你收集整理的USACO-Section2.2 Subset Sums的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。