usaco-2.2.2Subset Sums 集合
2024-08-30 04:48:34
01背包,对每个数至多取一次,为了避免重复,应倒序dp
usaco-2.2.2Subset Sums 集合
时间限制: 1 Sec 内存限制: 128 MB
题目描述
对于从1到N的连续整集合合,能划分成两个子集合,且保证每个集合的数字和是相等的。
举个例子,如果N=3,对于{1,2,3}能划分成两个子集合,他们每个的所有数字和是相等的:
- {3} and {1,2}
这是唯一一种分发(交换集合位置被认为是同一种划分方案,因此不会增加划分方案总数)
如果N=7,有四种方法能划分集合{1,2,3,4,5,6,7},每一种分发的子集合各数字和是相等的:
- {1,6,7} and {2,3,4,5}
{注
1+6+7=2+3+4+5} - {2,5,7} and {1,3,4,6}
- {3,4,7} and {1,2,5,6}
- {1,2,4,7} and {3,5,6}
给出N,你的程序应该输出划分方案总数,如果不存在这样的划分方案,则输出0。程序不能预存结果直接输出。
输入
输入文件只有一行,且只有一个整数N
输出
输出划分方案总数,如果不存在则输出0。
样例输入
7
样例输出
4
#include<cstdio>
#define ll long long
ll n,ji,dp[];
int main()
{
scanf("%lld",&n);
ji=n*(n+)/;
if(ji%){printf("");return ;}
ji>>=;dp[]=;
for(ll i=;i<=n;i++) for(ll j=ji;j>=i;j--) dp[j]+=dp[j-i];
printf("%lld",dp[ji]/);
}
最新文章
- Windows中使用TortoiseGit提交项目到GitLab配置
- intellij idea 插件 ideaVim
- Qt增加webp格式支持
- discuz注册 内部错误
- Unity Diffuse Metal Shader Mod
- 无缝滚动js (手写通俗易懂)
- CSS技巧!像table一样布局div
- lucene倒排索引缓冲池的细节
- 使用iframe父页面调用子页面和子页面调用父页面的元素与方法
- DFS实现排列组合
- c语言中的register int
- java中&;和&;&; | 和||的区别
- C51单片机_day_01(定时器和中断系统)
- spring校验注解
- debian系列下c++调用mysql, linux下面安装mysql.h文件
- win10安装mongodb-win32-x86_64-2008plus-ssl-3.4.10-signed
- 【JavaScript 6连载】一、关于对象(访问)
- JAVA学习笔记1——环境配置
- 在排序模型方面,点评搜索也经历了业界比较普遍的迭代过程:从早期的线性模型LR,到引入自动二阶交叉特征的FM和FFM,到非线性树模型GBDT和GBDT+LR,到最近全面迁移至大规模深度学习排序模型。
- [转]Excel.dll 导出Excel控制