uva 11151 Longest Palindrome (最长公共子序列)[通俗易懂]
大家好,又见面了,我是你们的朋友全栈君。
uva 11151 Longest Palindrome
A palindrome is a string that reads the same from the left as it does from the right. For example, I, GAG and MADAM are palindromes, but ADAM is not. Here, we consider also the empty string as a palindrome.
From any non-palindromic string, you can always take away some letters, and get a palindromic subsequence. For example, given the string ADAM, you remove the letter M and get a palindrome ADA.
Write a program to determine the length of the longest palindrome you can get from a string.
Input and Output
The first line of input contains an integer T (≤ 60). Each of the next T lines is a string, whose length is always less than 1000.
For ≥90% of the test cases, string length ≤ 255.
For each input string, your program should print the length of the longest palindrome you can get by removing zero or more characters from it.
Sample Input
2 ADAM MADAM
Sample Output
3 5
题目大意:求给出的字符串中最长的回文串。
解题思路:字符串的正序和逆序求最长公共子序列。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
char s[1005], s2[1005];
int dp[1005][1005], len;
void DP() {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++) {
if (s[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
}
int main() {
int T;
scanf("%d%*c", &T);
while (T--) {
gets(s);
len = strlen(s);
for (int i = len - 1; i >= 0; i--) {
s2[i] = s[len - i - 1];
}
DP();
printf("%d\n", dp[len][len]);
}
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/157216.html原文链接:https://javaforall.cn
相关文章
- [时间序列分析][4]–AR模型,MA模型,ARMA模型介绍[通俗易懂]
- 【说站】python序列操作的整理
- 多元时间序列特征工程的指南
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)- 基础练习 序列求和
- R语言用GARCH模型波动率建模和预测、回测风险价值 (VaR)分析股市收益率时间序列|附代码数据
- R语言k-Shape时间序列聚类方法对股票价格时间序列聚类|附代码数据
- MySQL:使用序列生成器轻松实现自增ID(mysql序列生成器)
- 如何在Oracle中删除包含序列的表?(oracle删除序列的表)
- SQL Server中新增序列技术实现主键自动增长(sqlserver加序列)
- 让Oracle表格拥有顺序序列(oracle 为表建序列)
- Oracle中如何创建序列及应用场景(oracle中序列的创建)
- Oracle中对象表视图索引序列过程等(oracle中对象包括)
- 在Oracle中使用序列实现声明的功能(oracle中声明序列)