随笔-141  评论-9  文章-3  trackbacks-0
USACO 2.2.2 Subset Sums

/*
ID: lorelei3
TASK: subset
LANG: C++
*/

#include<stdio.h>

const int N = 40;
const int MAX = (1+N)*N/4;

long long ans[N][MAX];

int main(){

    int n, tot, sum;

    freopen("subset.in", "r", stdin);    
    freopen("subset.out", "w", stdout);       
    
    scanf("%d", &n); 

    tot = (1+n)*n/2;

    if(tot&0x01){
        printf("0\n");
        return 0;
    }

    sum = tot/2;

    ans[1][0] = 1; ans[1][1] = 1;

    for(int i=2; i<=n; ++i)
        for(int j=0; j<=sum; ++j)
            if(j-i>=0)
                ans[i][j]=ans[i-1][j]+ans[i-1][j-i];
            else
                ans[i][j]=ans[i-1][j];

    printf("%lld\n", ans[n][sum]/2);

    return 0;
}
posted on 2010-11-21 00:48 小阮 阅读(175) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮