解题思路:正常模拟有点难以判断,但是这是一个经典的回文串,将字符串与自己的翻转串求最长公共子序列长度 ,字符串的长度减去最长子序列的长度 就是答案
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
string s;
char s1[1010],s2[1010];
int dp[1010][1010];//i到j的最长公共子序列长度
int main()
{
cin>>s;
int n=s.size();
for(int i=1;i<=n;i++) s1[i]=s[i-1];
for(int i=n;i>=1;i--) s2[i]=s1[n-i+1];
//找出最长公共子序列长度 n-最长就是答案
//套一下LCS的模板
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(s1[i]==s2[j]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
int ans=n-dp[n][n];
cout<<ans<<endl;
return 0;
}
0.0分
0 人评分
WU-拆分位数 (C++代码)浏览:786 |
剪刀石头布 (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:542 |
母牛的故事 (C语言代码)浏览:945 |
1126题解浏览:595 |
大家好,我是验题君浏览:577 |
1035 题解浏览:785 |
震宇大神的杀毒软件 (C语言代码)浏览:1080 |
A+B for Input-Output Practice (I) (C语言代码)浏览:431 |
多组数据新方法浏览:355 |