動(dòng)態(tài)規(guī)劃經(jīng)典題子集和問(wèn)題。
求子集和為總數(shù)的一半的子集的個(gè)數(shù)，按題意，還要再除以2。
int會(huì)溢出，要用long long.第一次提交就沒(méi)有注意到這個(gè)問(wèn)題。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("subset.in");
ofstream?fout("subset.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
long?long?dp[800];
void?solve()
{
????int?n;
????in>>n;
????int?sum?=?(n+1)*n/2;
????if(sum&1){
?????? //和為奇數(shù)，無(wú)解
????????out<<0<<endl;
????????return;
????}
????sum>>=1;
????dp[0]?=?1;
????for(int?i=1;i<=n;++i){
????????//從后向前，空間復(fù)雜度就降為O(n)了,具體可參考<背包問(wèn)題九講>
????????for(int?t?=?sum;t>=i;--t){
????????????dp[t]+=dp[t-i];
????????}
????}
????out<<dp[sum]/2<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}