AcWing 4997. 更小的数
原题链接
中等
作者:
liebe_1
,
2024-04-09 10:24:26
,
所有人可见
,
阅读 9
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 5010;
char g[N];
int dp[N][N];
//思路:一看到就是暴力搜索,发现超时,需要优化(起始位置和结束位置只能通过两层循环来确定,选择优化翻转字符串),发现是分割一部分字符串出来并且求解方案数,想到用dp(1表示满足条件,0表示不满足条件)
int main() {
long long ans = 0;
scanf("%s",g);
int n = strlen(g);
for(int len = 2; len <= n; len++) {//len = 1没有必要,此时i,j指向同一个字符串
for(int i = 0; i+len <= n; i++) {
int j = i+len-1;
if(g[i]>g[j])dp[i][j] = 1;
else if(g[i] == g[j])dp[i][j] = dp[i+1][j-1];
else dp[i][j] = 0;
if(dp[i][j] == 1)ans++;
}
}
printf("%lld",ans);
}