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; }