st[i][j]:判断i为左端点,j为右端点现在是否已经判断过;
tmp[i][j]:如果st[i][j]=true 那么tmp[i][j]就是以i为左端点,j为右端点交换是否是合法答案
区间dp容易出细节问题,我喜欢直接大力解决(doge
流程是一开始枚举所有左端点i和右端点j,如果能直接判断就记录st和tmp,不能就递归往i+1和j-1调用,判断一下临界点的情况就是j<=i的时候说明肯定不合法并返回,复杂度应该是n的平方多一点
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool st[5010][5010];
bool tmp[5010][5010];
ll cnt = 0;
string s;
bool check(int a, int b) {
if (st[a][b]) {
return tmp[a][b];
}
if (b <= a) {
st[a][b] = true;
tmp[a][b] = false;
return false;
}
if (s[b] - '0' < s[a] - '0') {
st[a][b] = true;
tmp[a][b] = true;
return true;
}
if (s[b] - '0' > s[a] - '0') {
st[a][b] = true;
tmp[a][b] = false;
return false;
}
if (check(a + 1, b - 1)) {
st[a][b] = true;
tmp[a][b] = true;
return true;
} else {
st[a][b] = true;
tmp[a][b] = false;
return false;
}
}
int main() {
// freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
int n = (int)s.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
check(i, j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (tmp[i][j]) {
cnt++;
}
}
}
cout << cnt << "\n";
return 0;
}
给自己顶一顶(●’◡’●)