题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^3)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main()
{
int ans=0;
string a;
cin>>a;
int len=a.size();
for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
for(int l=i,r=j;l<=r;l++,r--)
{
if(a[l]>a[r])
{
ans++;
break;
}
if(a[l]<a[r]) break;
}
}
}
cout<<ans;
return 0;
}
算法2
(区间DP)
时间复杂度 $O(n^2)$
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
bool f[5010][5010];//f[i][j]表示[i,j]段翻转后是否可以更小
//转移方程:if(a[i]<a[j]) f[i][j]=true;
// if(a[i]>a[j]) f[i][j]=false;
// if(a[i]==a[j]) f[i][j]=f[i+1][j-1];两个外位相同,则该区间是否成立取决于内位情况,
//显然长区间状态由短区间转移而来,故len从小到大枚举
int main()
{
int ans=0;
string a;
cin>>a;
int lena=a.size();
for(int len=2;len<=lena;len++)
{
for(int l=0;l+len-1<lena;l++)
{
int r=l+len-1;
if(a[l]>a[r]) f[l][r]=true;
else if(a[l]<a[r]) f[l][r]=false;
else f[l][r]=f[l+1][r-1];
if(f[l][r]) ans++;
}
}
cout<<ans;
return 0;
}