文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > USACO代码解析Subset Sums (subset)
侵权投诉

USACO代码解析Subset Sums (subset)

USACO代码解析Subset Sums (subset)

描述

对于从1到N (1 <= N <= 39) 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的。举个例子,如果N=3,对于{1,2,3}能划分成两个子集合,每个子集合的所有数字和是相等的:

{3} 和 {1,2}

这是唯一一种分法(交换集合位置被认为是同一种划分方案,因此不会增加划分方案总数) 如果N=7,有四种方法能划分集合{1,2,3,4,5,6,7},每一种分法的子集合各数字和是相等的:

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

{2,5,7} 和 {1,3,4,6}

{3,4,7} 和 {1,2,5,6}

{1,2,4,7} 和 {3,5,6}

给出N,你的程序应该输出划分方案总数,如果不存在这样的划分方案,则输出0。程序不能预存结果直接输出(不能打表)。

[编辑]格式

PROGRAM NAME: subset

INPUT FORMAT:

(file subset.in)

输入文件只有一行,且只有一个整数N

OUTPUT FORMAT:

(file subset.out)

输出划分方案总数,如果不存在则输出0。

[编辑]SAMPLE INPUT

7

[编辑]SAMPLE OUTPUT

4

n个数的总和为sum:=n*(n+1)shr 1,当且仅当sum为偶数的时候才有解,sum为奇数时直接输出0并且退出程序;

设分成的子集为set1,set2,sum=(n*(n+1)div 2)div 2. 设f[i,j]表示取前i个数,使set1总数和为j的方案数.第i个数的值为i,根据是否取第i个数就有:

f[i,j]=f[i-1,j]+f[i-1,j-i] j-i>=0

f[i,j]=f[i-1,j] j-i<0

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

long long a[40][40*(40+1)/2];

int main(){

freopen("subset.in", "r", stdin);

第1页

你可能喜欢

热门文档

相关文档

  • USACO 2.2 Subset Sums集合 解题报告

    USACO 2.2 Subset Sums集合 解题报告_IT/计算机_专业资料。USACO 2.2 Subset Sums集合 解题报告动态规划USACO 2.2 Subset Sums 集合 解题报告 OI 路程 2010-...

  • SECTION2.2.3 SUBSET SUMS

    暂无评价 13页 免费 A quadratic lower bound ... 暂无评价 12页 免费 USACO代码解析Subset Sums... 暂无评价 3页 1财富值喜欢此文档的还喜欢...

  • Spanning Subset Sums

    暂无评价 12页 免费 USACO代码解析Subset Sums... 暂无评价 3页 1财富值喜欢此文档的还喜欢 ACM+DP+算法++大集合 7页 2财富值...

  • Sure monochromatic subset sums by

    暂无评价 12页 免费 USACO代码解析Subset Sums... 暂无评价 3页 1财富值搜你所想,读你所爱 拒绝盗版,营造绿色文库 如要投诉违规内容,请到百度文库投诉中心...

  • USACO代码解析Packing Rectangles

    USACO代码解析Packing Rectangles_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Packing Rectangles描述 给定 4 个矩形块,找出一个最小的封闭矩形将这 4 个...

  • USACO代码解析The castle

    描述 我们憨厚的 USACO 主人公农夫约翰(Farmer John)以无法想象的运气,在他生日那天收到了一 份特别的礼物:一张“幸运爱尔兰”(一种彩票) 。结果这张彩票让他...

  • miller Concentrating Subset Sums at k Points

    24页 免费 Finding a Subset of Repr... 9页 5财富值 USACO 2.2 Subset Sums集合... 3页 5财富值 A quadratic lower bound ... 暂无评价 12页 免费...

  • USACO代码解析Preface Numbering (preface)

    USACO代码解析Preface Numbering (preface)USACO代码解析Preface Numbering (preface)隐藏>> 描述 一类书的序言是以罗马数字标页码的。 传统罗马数字用单个字母表示...

  • USACO代码解析Ordered Fractions (frac1)

    USACO代码解析Ordered Fractions (frac1)_工学_高等教育_教育专区。USACO代码解析Ordered Fractions (frac1)描述 输入一个自然数 N,对于一个最简分数 a/b 分子...

  • USACO代码解析Prime Palindromes (pprime)

    USACO代码解析Prime Palindromes (pprime)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Prime Palindromes (pprime)描述 因为 151 既是一个质数又是一个...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email