第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 D题-Toy模板网

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 D题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 D题

格式输入

输入一行包含一个长度为 n 的字符串表示 num（仅包含数字字符 0 ∼ 9），
从左至右下标依次为 0 ∼ n − 1。

格式输出

输出一行包含一个整数表示答案。

样例输入

210102

样例输出

8一共有 8 种不同的方案：
1）所选择的子串下标为 0 ∼ 1 ，反转后的 numnew = 120102 < 210102 ；
2）所选择的子串下标为 0 ∼ 2 ，反转后的 numnew = 012102 < 210102 ；
3）所选择的子串下标为 0 ∼ 3 ，反转后的 numnew = 101202 < 210102 ；
4）所选择的子串下标为 0 ∼ 4 ，反转后的 numnew = 010122 < 210102 ；
5）所选择的子串下标为 0 ∼ 5 ，反转后的 numnew = 201012 < 210102 ；
6）所选择的子串下标为 1 ∼ 2 ，反转后的 numnew = 201102 < 210102 ；
7）所选择的子串下标为 1 ∼ 4 ，反转后的 numnew = 201012 < 210102 ；
8）所选择的子串下标为 3 ∼ 4 ，反转后的 numnew = 210012 < 210102 ；

评测用例规模与约定

对于 20% 的评测用例，1 ≤ n ≤ 100 ；
对于 40% 的评测用例，1 ≤ n ≤ 1000 ；
对于所有评测用例，1 ≤ n ≤ 5000 。

解析

参考大佬题解，大佬自己的网站，很简约，喜欢的点个赞

参考程序


#include <iostream>
using namespace std;
const int N = 5001;
int ok[N][N];
inline void Case_Test() {
    string s;
    int n,ans=0;
    cin >> s;
    n = s.size();
    for (int d = 1; d < n; d++) {// 枚举区间间隔，保证每次处理完小区间
        for (int l = 0; l + d < n; l++) {// 枚举左端点
            int r = l + d;// 右断点
            if (s[l] > s[r]) ok[l][r] = 1;// 这个区间肯定可以
            else if (s[l] == s[r]) ok[l][r] = ok[l + 1][r - 1];// 看里面的区间
            ans += ok[l][r];
        }
    }
    cout << ans;
}
int main()
{
    Case_Test();
    return 0;
}