更小的数（暴力、区间DP）

解题思路:

dotcpp上暴力能过，但acwing上暴力只能过80%，考虑到前一个对比相同时我们要去找下一个对比，所以考虑记忆化搜索，因此想到区间DP，可以知道当a[l] == a[r]时，我们直接判断f[l+1][r-1]就能知道f[l][r]的状态了。

参考代码:

// 区间dp写法
#include <iostream>
#include <string>
using namespace std;

const int N = 5010;
string a;
bool f[N][N];

int main() {
	cin >> a;
	int n = a.size();
	int ct = 0;
	int res = 0;
	for (int len = 2; len <= n; len++) {
		for (int l = 0; l < n - len + 1; l++) {
			int r = l + len - 1;
			if (a[l] > a[r]) {
				f[l][r] = true;
				res++;
			}
			else if (a[l] == a[r]) {
				if (f[l + 1][r - 1])
					res++;
				f[l][r] = f[l + 1][r - 1];
			}
		}
	}
	cout << res;
	return 0;
}

// 暴力写法
#include <iostream>
#include <string>
using namespace std;

string a;

bool rev(int l, int r) {
	for (int i = l, j = r; i < j; i++, j--) {
		if (a[i] > a[j])
			return true;
		else if (a[i] < a[j])
			return false;
	}
	return false;
}

int main() {
	cin >> a;
	int n = a.size();
	int ct = 0;
	for (int len = n; len > 1; len--) {
		for (int l = 0; l < n - len + 1; l++) {
			int r = l + len - 1;
			if (rev(l, r))
				ct++;
		}
	}
	cout << ct;
	return 0;
}