[USACO][Section 2.2][背包] Subset Sums

题目大意：

给出一个整数n，求共有多少种方法能将[1,n]分成两个元素和相等的部分。

思路：

简单0/1背包，思路见代码。

代码：

/*
ID: lujunda1
LANG: C++
PROG: subset
*/
#include
#include
using namespace std;
long long f[781]={1};
//将f[0]初始化为1，其余初始化为0。 
int main()
{
    freopen("subset.in","r",stdin);
    freopen("subset.out","w",stdout);
    int n;
    scanf("%d",&n);
    int V=(1+n)*n/2;
    if(V%2)
    {
        printf("0\n");
        return 0;
    }
    V/=2;
    //V表示容量。 
    for(int i=1;i<=n;i++)
        for(int v=V;v>=i;v--)
            f[v]+=f[v-i];
    printf("%d\n",f[V]/2);
    //一种方法会出现两次。例如n=7时，{1、6、7}和{2、3、4、5}各出现一次。 
}