210102
201012
A1A2…An
An…A2A1
如何做,
翻转的是21,因为2>1;
翻转的是210,因为2>0;
翻转的是2101,因为2>1;
翻转的是21010,因为2>0;
翻转的是210102,因为2==2且1>0;
翻转的是10,因为1>0;
翻转的是1010,因为1>0;
翻转的是10,因为1>0
设置i,j分别指向头和尾,对于每一个i,遍历j,保证i<j,如果a[i]>a[j],可以,如果a[i]==a[j],查看下一个,即如果a[i+1]>a[j-1],可以,若相等,查看下一个,O(n^3),这里实际在找的是什么,写出代码,看看能不能优化
思考,对于f(i,j)存储区间[i,j]中,最小的ii,使得a[ii]>a[jj],ii+jj=i+j
a[i]>a[j],则f(I,j)=I,;
a[i]==a[j],f(I,j)=f(i+1,j-1);//和后面的相关,i+1还没有遍历到
a[i]<b[j],f(I,j)=-1(表示不存在) ******************待优化
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5050;
char a[N];
int main(){
scanf("%s",a);
//for(int i = 0;a[i];i++)
// printf("%c ",a[i]);
int res=0;
for(int i = 0;a[i];i++)
for(int j = i+1;a[j];j++)
{
if(a[i]>a[j])res++;
if(a[i]==a[j]){//寻找[i,j[区间内第一个ii<jj且a[ii]>a[jj]位置
int ii=i,jj=j;
while(ii<jj){
ii++;
jj--;
if(a[ii]>a[jj]){
res++;break;
}else if(a[ii]<a[jj])break;
}
}
//printf("%d %d %d\n",i,j,res);
}
printf("%d\n",res);
return 0;
}
平方差 找规律-推导-模拟暴力_wxxka的博客-CSDN博客
区间dp,先枚举区间长度
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=5050;
string s;
int f[N][N];
int n;
int res;
int main(){
cin>>s;
n=s.size();
for(int len = 1;len <= n;len++)
for(int i = 0;i+len-1<n;i++)//j-i=len-1,j<n
{
int j = i+len-1;
if(s[i]==s[j])f[i][j]=f[i+1][j-1];
else if(s[i]>s[j])f[i][j]=1;
res+=f[i][j];
}
cout<<res<<endl;
return 0;
}