USACO Section2.2 Subset Sums 解题报告 【icedream61】

　　　　subset解题报告
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　把1~N分成两组，让他们的和相等，请问这样的分组有多少种？
　　但顺序可以颠倒，比如{3}、{2,1}和{2,1}、{3}算作一种。
【数据范围】
　　1<=N<=39
【输入样例】
　　7
【输出样例】
　　4
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　01背包问题。
　　把每个数当做一个物品，那么有N件物品，编号i=1~N，分别对应数1~N；物品i的所占容量Ci=i。
　　背包容量V=N×(N+1)÷4；显然只有N%4==1或N%4==2时本题答案为0，否则答案便是把背包放满的方案数d[V]除以2的结果了。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　这题见过，不过这次做第一次却是分析错了。没有想得太细，觉得代码很短就写来试试了。不过我倒是觉得，再有这种情况，如果是考试，那我就好好分析去；但如果是实际问题，我还是会试试，毕竟只需要花上一点时间，去检验一下对错，怎么想都比分析来得划算。
　　自己又想了想，没想出解决方案，网上简单搜了下，看到了算法是01背包DP。于是把《背包九讲》重新温习了一遍，感觉比第一次看明白多了，很感谢崔添翼前辈！

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

 /*

 ID: icedrea1

 PROB: subset

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 int N;

 long long d[+];

 int main()

 {

     ifstream in("subset.in");

     ofstream out("subset.out");

     in>>N;

     if(N%==||N%==) out<<<<endl;

     else

     {

         int S=N*(N+)>>; // result is d[S,N]/2

         d[]=;

         for(int i=;i<=N;++i)

             for(int v=S;v>=i;--v) d[v]=d[v]+d[v-i];

         out<<d[S]/<<endl;

     }

     in.close();

     out.close();

     return ;

 }