题目描述

对于很多由 1∼N 构成的连续整数集合，我们都可以将其划分为两个子集，并使得两个子集的和相等。

例如，当 N=3 时，我们可以将集合 {1,2,3} 划分为子集 {1,2} 和 {3}，这也是唯一的一种满足条件的划分方式。

当 N=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，请你计算将 1∼N 构成的连续整数集合划分为和相等的两个子集，共有多少种划分方式。

将一种划分方式的某个子集内部的元素之间进行顺序调整仍看作是同一种划分方式。

输入格式
共一行包含整数 N。

输出格式
输出一个整数，表示划分方案数。

如果无法划分，则输出 0。

数据范围
1≤N≤39
输入样例：
7
输出样例：
4

算法

DP $O(n*sum)$,sum是所有数的总和除以2

其实这道题就是给定一个整数(所有1∼n的和/2),把他划分为若干个不大于n的互不相同的正整数之和的方法数/2(因为两组之间不计顺序)
1.分析状态:d(i,j):表示把整数i划分为不超过j的正整数的方法数(注意:不是除去2后的方法数)
2,阶段:第i个整数
3.分析边界:d(0,i)=d(i,0)=0;
4.分析目标:d(sum,n)/2
5.状态转移方程:d[i][j]=d[i-j][j-1]+d[i][j-1]; (只需要分类最大的数是否选择)

时间复杂度

O(16000)

C++ 代码

#include <cstdio>
#include <cstring>
using namespace std;

const int MX=400;
const int MY=40;

long long d[MX][MY];

int main()
{
    int n=0;
    scanf("%d",&n);

    //处理总和为奇数的情况
    if(n%4==1 || n%4==2)
    {
        printf("0\n");
        return 0;
    }

    memset(d,0,sizeof(d));

    int sum=0; //记录每一个子集的和
    for(int i=1;i<=n;i++)
        sum+=i;
    sum /= 2;

    for(int i=1;i<=sum;i++)
        for(int j=1;j<=n;j++)
            if(i>j)
                d[i][j]=d[i-j][j-1]+d[i][j-1]; //状态转移方程
            else if(i<j)
                d[i][j]=d[i][j-1];
            else
                d[i][j]=d[i][j-1]+1;

    printf("%lld\n",d[sum][n]/2); //因为一定有一组含有n
    return 0;
}