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);
USACO 2.2 Subset Sums集合 解题报告_IT/计算机_专业资料。USACO 2.2 Subset Sums集合 解题报告动态规划USACO 2.2 Subset Sums 集合 解题报告 OI 路程 2010-...
暂无评价 13页 免费 A quadratic lower bound ... 暂无评价 12页 免费 USACO代码解析Subset Sums... 暂无评价 3页 1财富值喜欢此文档的还喜欢...
暂无评价 12页 免费 USACO代码解析Subset Sums... 暂无评价 3页 1财富值喜欢此文档的还喜欢 ACM+DP+算法++大集合 7页 2财富值...
暂无评价 12页 免费 USACO代码解析Subset Sums... 暂无评价 3页 1财富值搜你所想,读你所爱 拒绝盗版,营造绿色文库 如要投诉违规内容,请到百度文库投诉中心...
USACO代码解析Packing Rectangles_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Packing Rectangles描述 给定 4 个矩形块,找出一个最小的封闭矩形将这 4 个...
描述 我们憨厚的 USACO 主人公农夫约翰(Farmer John)以无法想象的运气,在他生日那天收到了一 份特别的礼物:一张“幸运爱尔兰”(一种彩票) 。结果这张彩票让他...
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代码解析Ordered Fractions (frac1)_工学_高等教育_教育专区。USACO代码解析Ordered Fractions (frac1)描述 输入一个自然数 N,对于一个最简分数 a/b 分子...
USACO代码解析Prime Palindromes (pprime)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Prime Palindromes (pprime)描述 因为 151 既是一个质数又是一个...
热门文档