USACO 2.2 Subset Sums 集合（subset），usacosubset

USACO 2.2 Subset Sums 集合（subset），usacosubset

Description

對於從1到N的連續整集合，能劃分成兩個子集合，且保證每個集合的數字和是相等的。
舉個例子，如果N=3，對於{1，2，3}能劃分成兩個子集合，他們每個的所有數字和是相等的：

• {3} and {1,2}

這是唯一一種分法（交換集合位置被認為是同一種劃分方案，因此不會增加劃分方案總數）
如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分發的子集合各數字和是相等的:

• {1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
• {2,5,7} and {1,3,4,6}
• {3,4,7} and {1,2,5,6}
• {1,2,4,7} and {3,5,6}

給出N，你的程序應該輸出劃分方案總數，如果不存在這樣的劃分方案，則輸出0。程序不能預存結果直接輸出。

　　好  廢話不多說這是我在Ubuntu下打的第一個代碼，個人認為Ubuntu下很多界面較好  風格也還行（又說廢話了）。。。

　　這道題是一個dp  大致的意思是從1-n的每個數都給你一個  然後叫你找有多少種可能a+b+c...==x+y+z(當然a,b,c,x,y,都屬於這n個數）同時  這些數都要用完而且不能重復用   

　　剛剛看題目頗為不解  這用dp該怎麼做  明顯是坑爹嘛  後來實在想不出來就去baidu了（。。。）  然後看到一種普遍的解法就是看作一個01背包然後“

如果M=n*(n+1)/2是奇數，則沒有分法。如果是偶數，背包容量為M/2，dp[k] += dp[k-i],(i=1,2,...,n)計算k的時候為避免重算，

需倒著進行。”（這不還是看不懂嘛（請原諒我的愚笨））

　　再後來一想[1,n]這個區間裡所有數不久形成了一個a_n=n的等差數列嘛   那麼根據求和公式s_n=n+n*(n-1)/2 =n*(n+1)/2  既然這樣 要使兩邊相等 那麼

l(左邊的和)=r(右邊的和)=n*(n+1)/4  這樣的話如果算出來的n*(n+1)/4為小數的話那麼肯定就不可能有解了嘛  所以只要在開始判斷一下n*(n+1)/4能不能除盡（即判斷n*(n+1)%4是否為0）  然後如果除不盡就直接return 掉就行了。

　　在初步的判斷完以後  我們就要開始用dp大法了   可以看作有n個物品  給你n*(n+1)/4的質量   這一次的分法就等於這一次j比i多出來的數的分法加上原來i的分法       

　　代碼如下:

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn=10000+10;
 4 long long f[100000];
 5 int n,s;
 6 int main()
 7 {
 8     cin>>n;
 9     s=n*(n+1);
10     if(s%4!=0)
11     {
12         cout<<0<<endl;
13         return 0;
14     }
15     s/=4;
16     f[0]=1;
17     for(int i=1;i<=n;i++)
18         for(int j=s;j>=i;j--)
19             f[j]+=f[j-i];
20     cout<<f[s]/2<<endl;
21     return 0;
22 }