AcWing 4997. 更小的数(记忆化搜索
原题链接
中等
作者:
宫野龟宝
,
2024-04-12 14:19:56
,
所有人可见
,
阅读 8
记忆化搜索
好用!
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
char a[N];
int f[N][N];
int n, res;
int dp(int i, int j)
{
int &tmp = f[i][j];
if (tmp != -1) return tmp;
// 一开始写成当i == j时返回0了
// 想了一下:如果i+1=j,再往中间递归一次:i刚好=j+1
if (i > j) return 0;
tmp = 1;
if (a[i] > a[j]) tmp = 1;
else if (a[i] < a[j]) tmp = 0;
else tmp = dp(i + 1, j - 1);
res += tmp;
return tmp;
}
int main()
{
memset(f, -1, sizeof f);
scanf("%s", a + 1);
n = strlen(a + 1);
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ )
dp(i, j);
printf("%d\n", res);
return 0;
}