lightoj1033 - Generating Palindromes (LCS)

2024-08-24 12:38

本文主要是介绍lightoj1033 - Generating Palindromes (LCS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给你一个字符串,至少需要添加多少字符可以使得它变成一个回文串.

思路 :设串S的反串为S‘那么strlen(S) - LCS(S, S')就是本问题的答案.

如:

S(原串)       A   b  3  b  d

S1(倒序串)   d   b  3  b  A

LCS                   b  3  b

 

      所以,有3个字符已经配对,不用添加字符就能够成回文,需要添加的字母仅有“A”与“d”。

/************************************************ Author: fisty* Created Time: 2015-08-19 14:39:16* File Name   : 1033.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
#define MAX_N  1100
char s[MAX_N];
char _s[MAX_N];
int t;
int dp[MAX_N][MAX_N];
int solve(int n){Memset(dp, 0);for(int i = 1;i <= n; i++){for(int j = 1; j <= n; j++){if(s[i] == _s[j]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = max(dp[i-1][j], dp[i][j-1]) ;}}}return dp[n][n];
}
int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);scanf("%d", &t);int cnt = 1;while(t--){Memset(s, 0);Memset(_s, 0);scanf("%s", s+1);int n = strlen(s+1);for(int i = 1;i <= n; i++){_s[i] = s[n-i+1];}printf("Case %d: %d\n", cnt++,n - solve(n));   }return 0;
}


这篇关于lightoj1033 - Generating Palindromes (LCS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102505

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10066 LCS

题意: 最长公共子序列。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include

【UVA】11584-Partitioning by Palindromes(动态规划)

动态规划。 如果 j + 1 ~ i是回文,那么 dp[i] = min=(dp[j] + 1);  判断j + 1~ i是不是回文可以进行预处理,方法是枚举中心,之后向两边伸张,(需要枚举2次,一次是偶数回文,一次是奇数回文) 13993253 11584 Partitioning by Palindromes Accepted C++ 0.132 2014-08-05 08:2

NLP文本相似度之LCS

基础 LCS(Longest Common Subsequence)通常指的是最长公共子序列,区别最长公共字串(Longest Common Substring)。我们先从子序列的定义理解: 一个序列S任意删除若干个字符得到新的序列T,则T叫做S的子序列。 子序列和子串的一个很大的不同点是,子序列不要求连接,而子串要求连接。 两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y

USACO Section 1.5 Prime Palindromes

题意: 输入a和b  求 a和b之间所有既是素数同时又有回文性质的数  从小到大输出 思路: 如果枚举a到b之间所有的数再判断素数和回文那么复杂度会比O(n)还大  本题O(n)都会跪 因此思路转到能否 先得到所有素数再判断回文 或者 先得到所有回文的数在判断素数 本题我的做法是后者  说下原因 本题b最大为10^8  因此构造回文的数字可以枚举1~10000中的数字再对数字翻折

Queries for Number of Palindromes

~~~~~~       Queries for Number of Palindromes ~~~~~      总题单链接 思路 ~~~~~       设 g [ L ] [ R ] g[L][R] g[L][R] 表示区间 [ L , R ] [L,R] [L,R] 是否为回文串。 ~~~~~      预处理 g g g,枚举回文串的中点,从每个中点开始向两侧扩展,判断

最长公共子串(LCS)

(1) 找出两个字符串的最长公共子串 题目:输入两个字符串,找出两个字符串中最长的公共子串。 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。 #include<iostream>#include<string>using namespace std;int main(){string s1 = "GCCCTAGCCAGDE";string s2 = "GCGCCAGT

【CF245H】【Queries for Number of Palindromes】

H. Queries for Number of Palindromes time limit per test 5 seconds memory limit per test 256 megabytes input standard input output standard output You've got a string s = s1s2...

LCS转为LIS

(1) 先将所有数列排序。     第一维由小到大,当第一维相等时,第二维由大到小。   (排序规则亦可改成以第二个维度为主,最后则是找第一个维度的1DLIS。)       a     a    a     b     b    a     a     a    c     d   (0,6) (0,3) (0,2) (1,4) (1,1)(2,6) (2,3) (2,2) (3,5) (4,

【UVA10405】【裸LCS】

坑点在于输入有空格 #include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <list>#include <map>#include <set>#include <string>#include <cstdlib>#include <c