付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

大概的题意是: 给定一个序列 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 付翔 阅读(205) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜