P1466 [USACO2.2] 集合 Subset Sums
Koei
·
·
算法·理论
题意：
将一个1\sim n的集合划分成两个和相等的集合
问：方案数
思路：
设状态为:dp_{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;
}
```