AcWing 4997. 更小的数(区间dp)
原题链接
中等
作者:
逸误
,
2024-02-13 04:44:32
,
所有人可见
,
阅读 656
//最多能承受n^2的时间复杂度
//考点:区间dp!
#include <iostream>
#include <string>
using namespace std;
const int N = 5005;
string a;//char也可以比大小,输入后不用转化了
int dp[N][N];//dp[i][j]:左为i,右为j,这段是否符合是一种方案,若符合则为1
int res;
int main()
{
int n;
cin>>a;
n=a.size();//字符串方便之处:大小灵活!!
//区间dp必须从小区间dp到大区间
for(int len=2;len<=n;len++)
{
for(int l=0;l+len-1<n;l++)
{
int r=l+len-1;
if(a[l]>a[r])
{
res++;
dp[l][r]=1;
}
else if(a[l]==a[r])
{
res+=dp[l+1][r-1];
if(dp[l+1][r-1])
dp[l][r]=1;//加和更新两件事不要分开,容易忘!!
}
}
}
cout<<res<<endl;
return 0;
}