济南网站建设公司 推荐行知科技,文化网站模板,中医协会网站建设方案,深圳建设局官网站首页P9420 [蓝桥杯 2023 国 B] 子 2023 题目 分析代码 题目 分析
刚拿到这道题#xff0c;我大脑简单算了一下#xff0c;这个值太大了#xff0c;直观感觉就很难#xff01;#xff01;
但是#xff0c;你仔仔细细的一看#xff0c;先从最简单的第一步入手#xff0c;再… P9420 [蓝桥杯 2023 国 B] 子 2023 题目 分析代码 题目 分析
刚拿到这道题我大脑简单算了一下这个值太大了直观感觉就很难
但是你仔仔细细的一看先从最简单的第一步入手再第二步再第三…… 发现没有没错这就是最近一直在练的动态规划这是一个递推的过程由简单到复杂
那么应该怎么做呢从1写道2023unsigned long long都存不下这个数字为了保证不会溢出和方便遍历只能想到String类型了 string s; for (int i 1; i 2023; i) s to_string(i);//将i转换成string如何接上s的后面
既然是动态规划那用在哪呢我们定义dp[4]分别用 dp[0]表示当前可以组成2的数量。 dp[1]表示可以组成20的数量。 dp[2]表示可以组成202的数量。 dp[3]表示可以组成2023的数量。
接着就遍历字符串跟新对应dp[]数组的值
重点动态规划的题就是找到每一步之间的关系然后从头开始理由简单到复杂
代码
#include iostream
#include vector
#include string
#include algorithm
#include math.h
#include queue#include cctype
using namespace std;
long long dp[4];
string s;
int main() {for (int i 1; i 2023; i)s to_string(i);for (int i 0; i s.size(); i) {if (s[i] 2)dp[0], dp[2] dp[1];else if (s[i] 0)dp[1] dp[0];else if (s[i] 3)dp[3] dp[2];}cout dp[3] endl;return 0;
}
//输出5484660609
