洛谷P1028.数的计算(动态规划)
题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
1.不作任何处理;
2.在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3.加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入格式
1个自然数n(n≤1000)
输出格式
11个整数,表示具有该性质数的个数。
输入输出样例
输入
6
输出
6
(说明/提示:满足条件的数为:6,16,26,126,36,136)
我的分析
初看此题,顿觉简单:不就是递归嘛,穷举所有情况不就完了吗,岂能难得住我?( ̄▽ ̄)
说时迟那是快,我三下五除二地便写出如下解法:
#include<iostream>
using namespace std;
int func(int n){
int count=0;
for(int i=1;i<=n/2;++i){//枚举该数左边可能的相邻数
count += 1+fun(i);//仍是两种情况:左边无数/左边有数
}
return count;
}
int main(){
int n;
cin>>n;
int count=0;
count=1+func(n); //两种情况:左边无数/左边有数
cout<<count<<endl;
return 0;
}
然后我信心满满地等待着AC结果,然而却显示——
◢▆▅▄▃ 崩╰(〒皿〒)╯潰 ▃▄▅▆◣大部分case都没有过,我感觉收到了此题极大的羞辱!
于是,我不得不思考更高效的解法。如上所示,之前采取的递归的思路是自上而下:我们从原数开始逐步向左推进,分析该数左边可能出现的的所有数字排列。我灵机一动,不妨换一个思路,自下而上,从 1 分析起走,如数字 1 只有 1 种情况,就是 1 本身;数字 2 有 2 种情况: 2,12 ;数字 3 有 2 种情况: 3,13 ;数字 4 有 4 种情况: 4,24,14,124 …我们不难发现,前面的情况其实可以划归为后面出现的情况的子问题,如 12=1+2,124=12+4 等等,这也就是动态规划的基本思想:将复杂问题划归为简单的子问题,最终由基准情形逐步推导出所有情形。如果我们用 dp[i] 表示由数字 i 推导出的的所有满足性质的数的数量,那么有如下递推关系式:
dp[1]=1
dp[2]=1+dp[1]=2
dp[3]=1+dp[1]=2
dp[4]=1+dp[2]+dp[1]=4
dp[5]=1+dp[2]+dp[1]=4
dp[6]=1+dp[3]+dp[2]+dp[1]=6
…
dp[i]=1+dp[1,2,3,…,j] (j=i/2)
找准了基准情形: i=1 ,列出了递推式:dp[i]=1+dp[1,2,3,…,j] (j=i/2),那么动态规划的题目就迎刃而解啦。(ノ≧∀≦)ノ
该题的最终代码非常简洁,只有以下几行:
#include<iostream>
using namespace std;
int main(){
int n; //原数
cin>>n;
int dp[n+1]; //dp数组记录每种子问题的情况数
for(int i=1;i<=n;i++){//迭代以1-n结尾的每一个子问题
dp[i]=1; //只有该数自己本身算1种情形
for(int j=i/2;j>=1;j--){
dp[i] += dp[j]; //加上子问题的情形数
}
}
cout<<dp[n]<<endl;
return 0;
}
现在所有情况都能AC啦!
以后暴力求解时一定要三思而后行了…
最新文章
- 自己封装的Windows7 64位旗舰版,微软官网上下载的Windows7原版镜像制作,绝对纯净版
- Xcode8开发iOS10推送通知过程
- Unity Standard Assets 简介之 其他资源
- Flex(flash)检测摄像头的3种状态(是否被占用,没安装摄像头,正常)
- 元素间距属性(scrollLeft,scrollWidth,clientWidth,offsetWidth,padding,margin)
- WinForm GDI+自定义控件总结(一)
- Android 上传图片到 Asp.Net 服务器的问题
- js闭包用法
- 月見(つきみ) 夕(ゆう) SumiHui.墨虺
- CentOS7安装Hadoop2.7流程
- C++虚函数实现多态原理(转载)
- CNN计算过程
- ajaxfileupload批量上传文件+图片尺寸限制
- 2019-01-29 VS Code创建自定义Python代码片段
- 微信小程序之mpvue+iview踩坑之旅
- 卡尔曼滤波跟踪 opencv
- LogParse-Windows系统日志分析
- crash - JNI WARNING: input is not valid modified utf-8: illegal continuation byte
- java 中java.util.Arrays类---常用函数记录
- python3 raise HTTPError(req.full_url, code, msg, hdrs, fp) urllib.error.HTTPError: HTTP Error 403: Forbid
热门文章
- Monster Audio 使用教程 (八) Vst3 使用侧链功能
- vue学习(十) v-for循环普通数组 、对象数组、 迭代数字
- MySQL Front远程连接数据库
- XML--概念、约束、解析
- 不想得手指关节炎?帮你提炼IDEA常用代码补全操作
- 5分钟白嫖我常用的免费效率软件/工具!效率300% up!
- PHP quotemeta() 函数
- PHP mysqli_real_escape_string() 函数
- [转]Java死锁排查
- Docker之Ubuntu上使用Docker的简易教程