USACO-2.1Subset Sums

USACO--2.1Subset Sums

开始的时候，用dfs去做，结果果断超时；后面看了一下，原来就是一个0--1背包的变形题。

代码如下：

/*
ID: 15674811
LANG: C++
TASK: subset
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<fstream>
using namespace std;

int main()
{
         ///ofstream cout("subset.out");
         ///ifstream cin("subset.in");
         long long V[700];   ///答案的最大值超过了int的范围
         int n;
         while(cin>>n)
         {
               int sum=0;
               for(int i=1;i<=n;i++)
                    sum+=i;
               if(sum%2)
               {
                       cout<<"0"<<endl;
                       continue;
               }
               sum=sum/2;
               memset(V,0,sizeof(V));
               V[0]=1;
                for(int i=1;i<=n;i++)
                    for(int j=sum;j>=i;j--)
                    {
                          V[j]+=V[j-i];
                    }
                cout<<V[sum]/2<<endl;
         }
   return 0;
}