题目描述
小蓝有一个长度均为 $n$ 且仅由数字字符 $0 \\sim 9$ 组成的字符串,下标从 $0$ 到 $n − 1$,你可以将其视作是一个具有 $n$ 位的十进制数字 $num$,小蓝可以从 $num$ 中选出一段连续的子串并将子串进行反转,最多反转一次。
小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 $num_{new}$ 满足条件 $num_{new} < num$,请你帮他计算下一共有多少种不同的子串选择方案,只要两个子串在 $num$ 中的位置不完全相同我们就视作是不同的方案。
注意,我们允许前导零的存在,即数字的最高位可以是 $0$,这是合法的。
输入格式
输入一行包含一个长度为 $n$ 的字符串表示 $num$(仅包含数字字符 $0 \\sim 9$),从左至右下标依次为 $0 \\sim n − 1$。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 $20\\%$ 的评测用例,$1 ≤ n ≤ 100$;
对于 $40\\%$ 的评测用例,$1 ≤ n ≤ 1000$;
对于所有评测用例,$1 ≤ n ≤ 5000$。
输入样例:
210102
输出样例:
8
样例解释
一共有 $8$ 种不同的方案:
- 所选择的子串下标为 $0 \\sim 1$,反转后的 $num_{new} = 120102 < 210102$;
- 所选择的子串下标为 $0 \\sim 2$,反转后的 $num_{new} = 012102 < 210102$;
- 所选择的子串下标为 $0 \\sim 3$,反转后的 $num_{new} = 101202 < 210102$;
- 所选择的子串下标为 $0 \\sim 4$,反转后的 $num_{new} = 010122 < 210102$;
- 所选择的子串下标为 $0 \\sim 5$,反转后的 $num_{new} = 201012 < 210102$;
- 所选择的子串下标为 $1 \\sim 2$,反转后的 $num_{new} = 201102 < 210102$;
- 所选择的子串下标为 $1 \\sim 4$,反转后的 $num_{new} = 201012 < 210102$;
- 所选择的子串下标为 $3 \\sim 4$,反转后的 $num_{new} = 210012 < 210102$;
暴力
valid[l][r] 表示翻转 [l, r] 是否合法
数据比较小,直接暴力枚举所有方案,再判断其合法性即可
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5005;
char str[N];
bool valid[N][N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> str + 1;
int ls = strlen(str + 1);
int ans = 0;
for(int len = 2; len <= ls; len ++) //长度为1,等于没翻,从2开始考虑
{
for(int l = 1; l <= ls; l ++)
{
int r = l + len - 1;
if(r > ls) break;
if(str[l] > str[r]) valid[l][r] = true;
if(str[l] == str[r]) valid[l][r] = valid[l + 1][r - 1];
ans += (valid[l][r] == true);
}
}
cout << ans << endl;
return 0;
}