蓝桥杯 2023 省A 更小的数

admin2024-04-03  0

        蓝桥杯 2023 省A 更小的数,第1张

主要思路:

  1. 输入一个长度为n的字符串,用二维数组dp[i][j]来记录子串[i, j]是否需要反转一次才能满足条件。
  2. 使用动态规划自底向上地填充dp数组。
  3. 根据问题的要求,需要考虑字符串的子串中字符的大小关系来判断是否需要反转。
  4. 最后统计满足条件的子串的个数,即dp[i][j]为true的个数。
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    // 定义字符数组存储输入的字符串
    char s[5001];
    // 读取输入的字符串
    scanf("%s",s);
    // 获取字符串的长度
    int n=strlen(s);
    // 定义二维动态规划数组,dp[i][j]表示从i到j的子串是否需要反转一次才能满足条件
    vector<vector<bool> > dp(n,vector<bool>(n,false));

    int i,j;
    // 从字符串末尾开始向前遍历
    for(i=n-1; i>=0; i--)
    {
        // 从当前位置向后遍历字符串
        for(j=i+1; j<n; j++)
        {
            // 如果子串长度为1或2,只需比较第一个字符和最后一个字符的大小
            if(i==j-1 || i==j-2)
                dp[i][j] = s[i] > s[j] ? true : false;
            else
            {
                // 如果子串长度大于2,则需要根据动态规划的状态转移方程进行判断
                if(s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1];
                else if(s[i] > s[j])
                    dp[i][j] = true;
                else
                    dp[i][j] = false;
            }
        }
    }
    // 计数器,统计满足条件的子串个数
    int count = 0;
    // 遍历所有可能的子串
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            // 如果从i到j的子串需要反转一次才能满足条件,则计数器加1
            if(dp[i][j] == true)
                count++;
    // 输出满足条件的子串个数
    cout << count << endl;
    return 0;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!