解题思路:
所谓翻转,其实就是首尾相比,一段子串ij,如果右端点大于左端点,自然翻转后成立,右端点小于左端点翻转后肯定不成立,右端点等于左端点
翻转前后的首尾字符必然相等,只需比较i+1,j-1的大小。
先枚举长度,再枚举右端点
1.右端点大于左端点 则dp[i][j]=1;
2.右端点等于左端点,则可以看dp[i+1][j-1]是否为1,若为1,则dp[i][j]为1
3.右端点小于左端点,不进行任何操作
参考代码:
#include<bits/stdc++.h>
using namespace std;
char s[5050],dp[5050][5050]={0};
int main()
{
int ans=0,n;
cin>>s;
n=strlen(s);
int i,j,l;
for(i=0;i<=n-2;i++)
{
if(s[i]>s[i+1])
{
dp[i][i+1]=1;
ans++;
}
}
for(l=3;l<=n;l++)
{
for(i=0;i<=n-l;i++)
{
j=i+l-1;
if(s[i]>s[j])
dp[i][j]=1;
if(s[i]<s[j])
dp[i][j]=0;
if(s[i]==s[j])
dp[i][j]=dp[i+1][j-1];
if(dp[i][j]==1)
ans++;
}
}
cout<<ans;
return 0;
}
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复