Palindrome
Time Limit:3000MS |
|
Memory Limit:65536K |
Total Submissions:48933 |
|
Accepted:16817 |
Description
A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order
to obtain a palindrome.
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
Input
Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters
from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.
Output
Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.
Sample Input
5
Ab3bd
Sample Output
2#include<iostream>
using namespace std;
#define NUMMAX 5001
short int getLCS(char s1[],char s2[],int len1,int len2);
short int dp[NUMMAX][NUMMAX];
int main(){
int N;
cin>>N;
char s1[NUMMAX],s2[NUMMAX];
for(int i=1;i<=N;i++){
cin>>s1[i];
s2[N-i+1]=s1[i];
}
cout<<N-getLCS(s1,s2,N,N);
system("pause");
}
short int max(int a,int b){
return a>b?a:b;
}
short int getLCS(char s1[],char s2[],int len1,int len2){
for(int i=0;i<=len2;i++)
dp[0][i]=0;
for(int i=0;i<=len1;i++)
dp[i][0]=0;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(s1[i]==s2[j]){
dp[i][j]=max((dp[i-1][j-1]+1),dp[i][j]);
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[len1][len2];
}
解题报告copy之:
分类:POJ2013-01-26 09:14340人阅读收藏举报
题意:
给你一串字符串,让你求最少加入几个字符,才能使得这个字符串是个回文串。
做法:
设a[i]是这个字符串,b[i]是这个字符串的逆序串。
那么a[i],b[i]的最长公共子序列就是所求的字符串里拥有的最大的回文串。
然后用总串长减去最大的回文串长度即为所求。
求最长公共子序列的公式为:
dp[i][j]=max(dp[i-1] [j],dp[i][j-1])
if(a[i]==b[i])
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
如果直接求的话,势必要开一个5001*5001的数组,铁定MLE。
有一下两种解决方法:
1,开short int型数组
这是poj返回的结果:
2,运用动态数组。
根据dp滚动的过程我们可以知道,dp【i】【j】的值不会与dp[i-2][0.....n]的值有关系。
那么可以把dp[i][j]的值覆盖到dp[i-2][j]上。即dp[i][j]为dp[i%2][j];
poj返回的结果:
对比以上两种方法,显而易见的可以得出2的方法很节约空间,就是耗时略长。
1,short int数组
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #definemax(a,b)(a>b?a:b)
- usingnamespacestd;
- shortintdp[5001][5001];
- intmain()
- {
- inta[5001];
- intb[5001];
- inti,j;
- intn;
- charstr;
- cin>>n;
- getchar();
- for(i=1;i<=n;i++)
- {
- scanf("%c",&str);
- a[i]=str;
- b[n-i+1]=str;
- }
- for(i=0;i<=n;i++)
- {
- dp[i][0]=0;
- dp[0][i]=0;
- }
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=n;j++)
- {
- dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
- if(a[i]==b[j])
- {
- dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
- }
- }
- }
- intlen;
- len=dp[n][n];
- printf("%d\n",n-len);
- return0;
- }
2,滚动数组
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- usingnamespacestd;
- intmain()
- {
- inta[5001];
- intb[5001];
- intdp[10][5001];
- inti,j;
- intn;
- charstr;
- cin>>n;
- getchar();
- for(i=1;i<=n;i++)
- {
- scanf("%c",&str);
- a[i]=str;
- b[n-i+1]=str;
- }
- dp[1][0]=dp[0][0]=0;
- for(i=0;i<=n;i++)
- {
- dp[0][i]=0;
- }
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=n;j++)
- {
- dp[i%2][j]=max(dp[i%2][j-1],dp[(i-1)%2][j]);
- if(a[i]==b[j])
- {
- dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j-1]+1);
- }
- }
- }
- intlen;
- len=dp[n%2][n];
- printf("%d\n",n-len);
- return0;
- }
题意:
给你一串字符串,让你求最少加入几个字符,才能使得这个字符串是个回文串。
做法:
设a[i]是这个字符串,b[i]是这个字符串的逆序串。
那么a[i],b[i]的最长公共子序列就是所求的字符串里拥有的最大的回文串。
然后用总串长减去最大的回文串长度即为所求。
求最长公共子序列的公式为:
dp[i][j]=max(dp[i-1] [j],dp[i][j-1])
if(a[i]==b[i])
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
如果直接求的话,势必要开一个5001*5001的数组,铁定MLE。
有一下两种解决方法:
1,开short int型数组
这是poj返回的结果:
2,运用动态数组。
根据dp滚动的过程我们可以知道,dp【i】【j】的值不会与dp[i-2][0.....n]的值有关系。
那么可以把dp[i][j]的值覆盖到dp[i-2][j]上。即dp[i][j]为dp[i%2][j];
poj返回的结果:
对比以上两种方法,显而易见的可以得出2的方法很节约空间,就是耗时略长。
1,short int数组
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #definemax(a,b)(a>b?a:b)
- usingnamespacestd;
- shortintdp[5001][5001];
- intmain()
- {
- inta[5001];
- intb[5001];
- inti,j;
- intn;
- charstr;
- cin>>n;
- getchar();
- for(i=1;i<=n;i++)
- {
- scanf("%c",&str);
- a[i]=str;
- b[n-i+1]=str;
- }
- for(i=0;i<=n;i++)
- {
- dp[i][0]=0;
- dp[0][i]=0;
- }
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=n;j++)
- {
- dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
- if(a[i]==b[j])
- {
- dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
- }
- }
- }
- intlen;
- len=dp[n][n];
- printf("%d\n",n-len);
- return0;
- }
2,滚动数组
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- usingnamespacestd;
- intmain()
- {
- inta[5001];
- intb[5001];
- intdp[10][5001];
- inti,j;
- intn;
- charstr;
- cin>>n;
- getchar();
- for(i=1;i<=n;i++)
- {
- scanf("%c",&str);
- a[i]=str;
- b[n-i+1]=str;
- }
- dp[1][0]=dp[0][0]=0;
- for(i=0;i<=n;i++)
- {
- dp[0][i]=0;
- }
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=n;j++)
- {
- dp[i%2][j]=max(dp[i%2][j-1],dp[(i-1)%2][j]);
- if(a[i]==b[j])
- {
- dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j-1]+1);
- }
- }
- }
- intlen;
- len=dp[n%2][n];
- printf("%d\n",n-len);
- return0;
- }
分享到:
相关推荐
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1159-Palindrome
Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
Palindrome Sub-Array,Problem Description A palindrome sequence is a sequence which is as same as its reversed order. For example, 1 2 3 2 1 is a palindrome sequence, but 1 2 3 2 2 is not. Given a 2-...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
欧拉公式求长期率的matlab代码欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大回文数为9009...
palindrome number in c
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
欧拉计划 问题 两个三位数的最大回文乘积是多少? 背景 回文数在两个方向上都相同。 例如, 101是回文, 91,519和1,111也是91,519 。 例如,由两个两位数的乘积构成的最大... 在Learn.co上查看 ,并开始免费学习编码。
使用堆栈检查回文作者:思南博乐 ( )描述我构建了这个小例子来说明如何使用数组实现堆栈到 Severna Park 高中的 CS 俱乐部。
欧拉公式求长期率的matlab代码 JavaScript双碱基回文挑战 在这个挑战中,您将完成。 欧拉计划(Project Euler)是可以用许多编程语言解决的数学问题的集合。 这是一个有用的网站,可用于练习白板或掌握您知道或想要...