C时间限制:1 毫秒 | C内存限制:65535 Kb
题目内容:
对于由从1到N(1<=N<=39)这N个连续的整数组成的集合来说,我们有时可以将集合分成两个部分和相同的子集合。
例如,N=3时,可以将集合{1,2,3}分为{1,2}和{3}。此时称有一种方式(即与顺序无关)。
N=7时,共有四种方式可以将集合{1,2,3,...,7}分为两个部分和相同的子集合:
{1,6,7}和{2,3,4,5}
{2,5,7}和{1,3,4,6}
{3,4,7}和{1,2,5,6}
{1,2,4,7}和{3,5,6}
输入描述
程序从标准输入读入数据,只有一组测试用例。如上所述的N。
输出描述
方式数。若不存在这样的拆分,则输出0。
输入样例
7
输出样例
4
思路:
这道题我开始只有一点思路,就是关于这个数加还是不加,想到dfs,但是又想到它无法记得我加了哪个数,无法实现,然后看了别人的博客
用动态规划,这个真的有点意思。
dp[i][sum] 中i代表的是i这个数,sum代表的是子集和的整数被限制为sum,然后从加还是不加i这个数进行分类
1.如果i==0 ,sum==0,这里很关键,就是把0放入这个子集和为0 的集合中,方案数为1;
2.当i==0,sum>0,无法放入,所以方案数为0;
3.i>sum,就是说这个数大于这个被限制为数值为sum的子集和,所以无法放入,因此为dp[i-1][sum];
4.i<=sum,这里需要分类讨论,i这个数有资格放入这个集合中,但是可以放也可以不放,所以为dp[i-1][sum](不放的方案数)+dp[i-1][sum-i](放的方案数),dp[i-1][sum-i]含义:我们要把i这个数放入这个集合中,所以我们要预先就留i这么大的空间,所以我们只有数值为sum-i的子集和
代码:
#include<iostream> #include<stdio.h> using namespace std; const int maxn = 2e3+10; int dp[50][maxn]; int main(){ int n; cin>>n; int sum; sum = (1+n)*n/2; if(sum%2==1) cout<<"0"<<endl; else{ sum = sum/2; dp[0][0] = 1; for(int i=1;i<=n;i++) dp[0][i] = 0; for(int i=1;i<=n;i++){ for(int j=0;j<=sum;j++){ if(j<i) dp[i][j] = dp[i-1][j]; else dp[i][j] = dp[i-1][j]+dp[i-1][j-i]; } } cout<<dp[n][sum]/2<<endl; } return 0; }