P9420 [蓝桥杯 2023 国 B] 子 2023
P9420 [蓝桥杯 2023 国 B] 子 2023
- 题目
- 分析
- 代码
题目
分析
刚拿到这道题，我大脑简单算了一下，这个值太大了，直观感觉就很难！！
但是，你仔仔细细的一看，先从最简单的第一步入手，再第二步，再第三……
发现没有！！没错！这就是最近一直在练的动态规划，这是一个递推的过程，由简单到复杂
那么应该怎么做呢？从1写道2023，unsigned 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