P1466 [USACO2.2] 集合 Subset Sums

题意：

将一个

1\sim n

的集合划分成两个和相等的集合

问：方案数

思路：

设状态为:

dp_{i,j}

i

表示在前

i

个数中选数，而和为

j

，所以状态转移方程为：

dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-a_i}

程序：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e4+10);
int n,sum(0);
int a[maxn];
int dp[maxn][maxn];
int main(){
    cin>>n;
    for(int i(1);i<=n;i++){
        a[i]=i;
    }
    sum=n*(n+1)/2;
    if(sum%2){
        cout<<"0\n";
        return 0;
    }
    dp[0][0]=1;
    for(int i(1);i<=n;i++){
        for(int j(1);j<=sum;j++){
            dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
        }
    }
    cout<<dp[n][sum/2]<<'\n';
    return 0;
}

P1466 [USACO2.2] 集合 Subset Sums

文章操作

题意：

思路：

程序：

相关推荐

评论

P1466 [USACO2.2] 集合 Subset Sums