蓝桥杯刷题-14-更小的数-区间DP⭐
蓝桥杯2023年第十四届省赛真题-更小的数
//区间DP
#include <iostream>
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+10;
int f[N][N];
void solve(){string s;cin>>s;int ans=0;for(int len=2;len<=s.size();len++){for(int l=0;l+len-1<s.size();l++){int r=l+len-1;if(s[l]>s[r])f[l][r]=1;else if(s[l]==s[r]){f[l][r]=f[l+1][r-1];}ans+=f[l][r];}}cout<<ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--)solve();}