Contest1593 - 2018-2019赛季多校联合新生训练赛第三场(部分题解)
2024-10-09 18:53:32
H 10255 自然数无序拆分
题干:
题目描述
美羊羊给喜羊羊和沸羊羊出了一道难题,说谁能先做出来,我就奖励给他我自己做的一样礼物。沸羊羊这下可乐了,于是马上答应立刻做出来,喜羊羊见状,当然也不甘示弱,向沸羊羊发起了挑战。
可是这道题目有一些难度,喜羊羊做了一会儿,见沸羊羊也十分头疼,于是就来请教你。
题目是这样的:
把自然数N(N<=)分解为若干个自然数之和,求出有几种情况。
如N=5时,有7种情况
=++++
=+++
=++
=++
=+
=+
=
怎么样?你要加油帮助喜羊羊哦! 输入
一个自然数N(N<=) 输出
无序拆分的种数。 样例输入 样例输出
题解:
考察知识点:有关计数问题的DP
求自然数n的无序拆分的种数可以转化成求"n的划分种数"
AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=+; int n;
int dp[maxn][maxn];//dp[i][j] : j的i划分方案数 int main()
{
scanf("%d",&n);
dp[][]=;
for(int j=;j <= n;++j)
for(int i=;i <= n;++i)
if(j < i)//当j不足矣划分成i份时
dp[i][j]=dp[i-][j];
else//dp[i-1][j] : 含ai=0的划分总方案数,dp[i][j-i] : 不含ai=0的总方案数
dp[i][j]=dp[i-][j]+dp[i][j-i];
printf("%d\n",dp[n][n]); return ;
}
题目来源:2009年慈溪市小学生计算机程序设计比赛
最新文章
- Java学习笔记--循环总结
- JavaScript零基础学习系列一
- RecyclerView item 状态错乱
- 回到顶端js实现
- 【Storage】Ubuntu LVM 安装配置
- ELK_日志分析系统Logstash+ElasticSearch+Kibana4
- CTSC&;&;APIO 2015 酱油记
- BAT及各大互联网公司前端笔试面试题--Html,Css篇
- hdu 1576 A/B (扩展欧几里德简单运用)
- Cocos2d-x优化中多线程并发訪问
- Mysql动态多条件查询
- 关于ajax的那些事
- 「OC」构造方法和分类
- a元素的两个重要功能和表格布局
- 云如何让App开发更简单?
- ArcGIS——2015年中国各省GDP总量分级图(6等级)
- 解决No converter found for return value of type: class java.util.ArrayList
- AtCoder Regular Contest 101 (ARC101) D - Median of Medians 二分答案 树状数组
- Moving Tables---(贪心)
- c# 数组协变