子串--子字符串 0528

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;	
}