解题思路
区间DP
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int N=5e3+10;
int n;
char str[N];
int dp[N][N];
int main()
{
cin>>str;
n=strlen(str);
int cnt=0;
for(int len=2;len<=n;len++)
for(int l=0;l+len-1<n;l++)
{
int r=l+len-1;
if(str[l]>str[r])
{
dp[l][r]=1;
cnt++;
continue;
}
else if(str[l]<str[r])
{
dp[l][r]=0;
continue;
}
else if(str[l]==str[r])
{
dp[l][r]=dp[l+1][r-1];
if(dp[l][r])
cnt++;
continue;
}
}
cout<<cnt;
return 0;
}