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; }