AcWing 4997. 更小的数
原题链接
中等
作者:
shangfei
,
2024-04-07 21:32:36
,
所有人可见
,
阅读 4
暴搜优化(记忆化搜索)
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
char a[N];
int f[N][N];
bool dfs(int i, int j)
{
int &t = f[i][j];
if(~t) return t;
if(i >= j) return t = false;
if(a[i] > a[j]) return t = true;
else if(a[i] < a[j]) return t = false;
else return t = dfs(i+1, j-1);
}
int main()
{
int cnt = 0;
scanf("%s", a+1);
int n = strlen(a+1);
memset(f, -1, sizeof f);
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j < i ; j++)
if(dfs(j, i))
cnt++;
cout << cnt << endl;
return 0;
}