更小的数

• ==问题描述==
• ==格式输入==
• ==格式输出==
• ==样例输入==
• ==样例输出==
• ==评测用例规模与约定==
• ==解析==
• ==参考程序==

问题描述

格式输入

输入一行包含一个长度为 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 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;}

以个人刷题整理为目的，如若侵权，请联系删除~