洛谷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啦!
以后暴力求解时一定要三思而后行了…
相关文章
- 500行SQL快速实现UCF
- 比 SQL 快?这个数据库神器强的离谱!
- 分库分表实战:新的挑战—千万级数据优化之垂直拆分
- 一块GPU模拟猴子大脑,普通台式机变超算,英国大学研究登上Nature子刊
- 银行核心系统分布式改造,架构设计如何为数据库运维加成?
- No.5时序数据库随笔 - NaN的支持
- No.4时序数据库随笔 - 安装
- 6.6K Star!比 Pandas 快很多的数据处理库
- 一款深受用户欢迎的HTAP数据库,PingCAP做对了什么?
- 分库分表实战:竿头日上—千万级数据优化之读写分离
- 一篇带给你Redis中Bitmap的妙用
- No.2时序数据库随笔 - IoTDB核心技术剖析
- No.1-时序数据库随笔 - 时序数据库综述
- 面试官:为什么 Redis 要有哨兵?
- 2023年超过1000量子比特!IBM公布量子计算开发路线图
- 火了十年,两万字聊聊数据湖的发展史
- 2021年7种软件开发职位的技能需求
- Undo 日志用什么存储结构支持无锁并发写入?
- Apache Doris刚“毕业”:为什么应关注这种SQL数据仓库?
- 面试突击:MySQL 中如何去重?