本文共 2111 字,大约阅读时间需要 7 分钟。
共一行,包含一个由大写字母ABCD构成的字符串,表示现在看到的密码串。
输出一个整数,表示至少脱落了多少个种子。
输入字符串长度不超过1000
ABCBA
0
ABDCDCBABC
3
将当前字符串加上若干字母使其变为回文串,其实就是将多余的字母对应位置加上对应的字母.
所以这题也可以转化为删除多少字符使其变为回文串. 一种方法是将字符串倒转,求出他的最长公共子序列,这样就可以比较便利地求出来,最长组成回文串子序列的长度. 另一种是区间dp的方式,我们的思路是从两端向中间靠拢,选判断边界相等的问题. 如果边界两个字符是相等的,那么直接当前区间的最长回文串子序列+2, 如果是不相等的情况下,就要判断是包含左端点不包含右端点的长度长,还是包含右端点不包含左端点的长度长, 这一点的思路是和最长公共子序列的思路是一样的. 当然还有左右端点都不选的状态,但是选的话一定是大于等于的状态,所以就不用考虑都不选的情况了 所以转移方程就是if(s[l]==s[r]) dp[l][r]=dp[l+1][r-1]+2;else{ dp[l][r]=max(dp[l+1][r],dp[l][r]); dp[l][r]=max(dp[l][r-1],dp[l][r]);}
区间dp求最长回文子序列
#include#include #include #include using namespace std;const int maxn=1e3+5;int dp[maxn][maxn];int main(){ string s; cin>>s; int slen=s.size(); for(int len=1;len<=slen;len++) { for(int l=0;l+len-1
将字符串反转求最长回文子序列
#include#include #include #include using namespace std;const int maxn=1e3+5;int dp[maxn][maxn];int main(){ string s; cin>>s; int slen=s.size(); string a=s; reverse(a.begin(),a.end()); for(int i=1;i<=slen;i++) { for(int j=1;j<=slen;j++) { if(a[i-1]==s[j-1]) dp[i][j]=dp[i-1][j-1]+1; else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } cout< <
DFS做法,不间接求,直接是求使字符串变回文的思路,不过还是区间dp的思想
#include#include using namespace std;const int N = 1e3 + 5;int f[N][N];string str;int dfs(int l, int r){ if (f[l][r]) return f[l][r]; if (l >= r) return 0; int res; if (str[l] != str[r]) res = min(dfs(l, r-1)+1, dfs(l+1, r)+1); else res = dfs(l+1, r-1); return f[l][r] = res;}int main(){ cin >> str; cout << dfs(0, str.size()-1); return 0;}
转载地址:http://jhagz.baihongyu.com/