大概的題意是： 給定一個序列 1 。。N ，假設全集為U那么存在多少種情況 ： 兩個子集A B其中A∩B=∅ ，A∪B=U ，A元素的和== B元素的和。
開始寫了個遞歸，枚舉，提交超時：void work(int deep,int start)
{
if(deep >= n) return;
if(ans > (sum -ans)) return ;
if(ans == sum-ans)
{
gcount ++;
/*FOR_1(i,1,n){
if(used[i] == 1)
fout<<i<< " ";
}
fout<<endl;*/
return ;
}
FOR_1(i,start + 1,n){
if(used[i] == 0){
used[i] = 1;
ans += i;
work(deep + 1,i);
used[i] = 0;
ans -= i;
}
}
}
之后改用另外一種思路，f(n,ans) = f(n-1,ans-n) + f(n-1,ans) ,這個有點分治的思路，把問題的規模逐漸縮小，從而得到解。中間加了個優化，用一個二維數組存下中間計算的結果，這樣就不會超時。
/*
ID:fuxiang2
PROG: subset
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <stack>
#include <
string>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <
set>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
using namespace std;
ofstream fout ("subset.out");
ifstream fin ("subset.in");
const int N = 40;
int used[N];
int n ;
int sum;
int ans ;
int gcount ;
int data[40][800];
void work(
int deep,
int start)
{
if(deep >= n)
return;
if(ans > (sum -ans))
return ;
if(ans == sum-ans)
{
gcount ++;
/*FOR_1(i,1,n){
if(used[i] == 1)
fout<<i<< " ";
}
fout<<endl;*/
return ;
}
FOR_1(i,start + 1,n){
if(used[i] == 0){
used[i] = 1;
ans += i;
work(deep + 1,i);
used[i] = 0;
ans -= i;
}
}
}
int solve(
int n ,
int ans)
{
int msum = (n+1)*n/2;
if(ans <= 0)
return 0;
if(msum < ans)
return 0 ;
else if(msum == ans )
return 1 ;
if(data[n][ans] )
return data[n][ans] ;
data[n-1][ans-n] = solve(n-1,ans-n);
data[n-1][ans] = solve(n-1,ans);
return data[n-1][ans-n] + data[n-1][ans];
}
int main()
{
fin>>n;
sum = (1+n)*n/2;
ans = 0;
if(sum%2 ==1){
fout<<"0"<<endl;
}
else {
//work(0,0);
//fout<<gcount/2 <<endl;
int re = solve(n,sum/2);
fout<<re<<endl;
}
//int re = solve(n,sum/2);
//fout<<re<<endl;
return 0;
}
原始博客地址：http://www.fuxiang90.com/2012/07/usaco2-2-subset-sums/
posted on 2012-07-26 23:16
付翔 閱讀(302)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構