蓝桥杯“子2023“十四届真题C++题解

以下是我的解题方案

1. #include <iostream>
2. using namespace std;
3. int main(){
4.     long long dp[4]={0};
5.     for(int i=1;i<=2023;++i){
6.         string num = to_string(i);
7.         for(char c:num){
8.             if(c=='2'){
9.                 dp[2]+=dp[1];
10.                 dp[0]+=1;
11.             }else if(c=='0'){
12.                 dp[1]+=dp[0];
13.             }else if(c=='3'){
14.                 dp[3]+=dp[2];
15.             }
16.         }
17.     }
18.     cout<<dp[3]<<endl;
19.     return 0;
20. }

复制代码

初始化动态规划数组：

1. long long dp[4] = {0};

复制代码

• dp[0]: 以 '2' 结尾的子序列个数。
  
• dp[1]: 以 '20' 结尾的子序列个数。
  
• dp[2]: 以 '202' 结尾的子序列个数。
  
• dp[3]: 以 '2023' 结尾的子序列个数。
  

遍历所有数字：

1. for(int i=1; i<=2023; ++i){
2.     string num = to_string(i);
3.     ...
4. }

复制代码

• 枚举从 1 到 2023 的所有数字。
  
• 将每个数字转换为字符串情势，便于逐字符处理。
  

逐字符更新动态规划状态：

1. for(char c : num){
2.     if(c=='2'){
3.         dp[2] += dp[1]; // "20" 扩展为 "202"
4.         dp[0] += 1;     // 新的以 "2" 结尾的子序列
5.     }else if(c=='0'){
6.         dp[1] += dp[0]; // "2" 扩展为 "20"
7.     }else if(c=='3'){
8.         dp[3] += dp[2]; // "202" 扩展为 "2023"
9.     }
10. }

复制代码

遍历当前数字字符串的每个字符：

• 如果是 '2'：
  
  
  
  • 扩展之前以 '20' 结尾的子序列为 '202'。
    
  • 新增一个以 '2' 结尾的子序列。
    
  
  
• 如果是 '0'：
  
  
  
  • 扩展之前以 '2' 结尾的子序列为 '20'。
    
  
  
• 如果是 '3'：
  
  
  
  • 扩展之前以 '202' 结尾的子序列为 '2023'。
    
  
  

输出效果：

1. cout << dp[3] << endl;

复制代码

终极，dp[3] 存储的就是以 '2023' 为子序列的个数。

核心逻辑分析

• 本质上是一个动态规划标题，此中每个状态依赖于上一个状态的效果：
  
  
  
  • dp[0] 表现所有可能以 '2' 结尾的子序列。
    
  • dp[1] 利用 dp[0] 来扩展到以 '20' 结尾。
    
  • dp[2] 利用 dp[1] 来扩展到以 '202' 结尾。
    
  • dp[3] 利用 dp[2] 来扩展到以 '2023' 结尾。
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。