USACO:Subset Sums簡単dp
690 ワード
/*
ID: Jang Lawrence
PROG: subset
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define mp make_pair
using namespace std;
int n;
long long dp[800];
int main()
{
#ifndef DEBUG
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
#endif
scanf("%d",&n);
int k=n*(n+1)/2;
if(k&1) {puts("0");return 0;}
else
{
k/=2;
dp[0]=1;
for(int i=1;i<=n;++i)
for(int j=k;j>=i;--j)
dp[j]+=dp[j-i];
printf("%lld
",dp[k]/2);
}
return 0;
}