P1466 Subset Sum

发布时间 2023-08-23 15:12:01作者: 失控D大白兔

对于从 1∼n 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的
求可以划分的方案数

1. 动态规划

long long maxval(int n){ 
    int sum = (1+n)*n/2;
    if(sum%2==1) return 0;
    vector<long long> dp(sum+1)
    dp[0] = 1;//边界方案数为1
    for(int i=1;i<=n;i++)
        for(int j=sum;j>=i;j--)
            dp[j]+=dp[j-i];
    return dp[sum/2]/2;
}