POJ 1159 - Palindrome (LCS, 滚动数组)

时间:2022-09-03 12:24:45
Palindrome
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 55018   Accepted: 19024

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

【题意】 给你一个长度为n的字符串,问最少再添多少字符能组成一个回文串;
【分析】
原字符串:Ab3bd
翻转后串:db3ba
二者有重复子串b3b,若想构成回文串,必须要再添加除重复子串外的其他字符。如:Adb3bdA 下面的问题就是求原字符串与翻转后串的最长公共子串,即LCS问题; 【LCS问题】
标记s1,s2字符位置变量i,j,令dp[i][j]为字符串s1[1~i],s2[1~j]的最长公共子串的长度;可知状态转移方程如下:
dp[i][j] = s1[i] == s2[j] ? dp[i-1][j-1] : max(dp[i-1][j], dp[i][j-1]); 【注意】
对于本题,n的范围是[3,5000],若直接开5000*5000的二维数组会内存超限(当然听说用short int会AC飘过); 【滚动数组】
滚动数组的作用在于优化空间。主要应用在递推或动态规划中(如01背包问题)。因为DP题目是一个自底向上的扩展过程,我们常常需要用到的是连续的解,前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在n很大的情况下可以达到压缩存储的作用。 例如本题,dp[i][j]的值仅仅取决于dp[i-1][j-1], dp[i][j-1], dp[i-1][j];再直白地说,只需要保留下i-1时的状态,就可以求出i时的状态;所以dp完全可以只开一个2*5000的数组求解;
或许有人问j为什么不能也开成2? 这很好说明,因为j是随i不断循环的,i增加一个j全部循环一次,所以i在不断变化时需要不断j全部的信息,我们完全也可以令i随j不断变化,这样仅仅改变成5000*2,其他完全一样; 【代码】
 /*LCS*/

 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn = ;
char s1[maxn], s2[maxn];
int n;
int dp[][maxn]; void LCS()
{
memset(dp, , sizeof(dp)); for(int i = ; i <= n; i++)
{
for(int j = ; j <= n; j++)
{
//cout << s1[i] << " " << s2[j] << endl;
if(s1[i] == s2[j])
dp[i%][j] = dp[(i-)%][j-]+;
else
dp[i%][j] = max(dp[(i-)%][j], dp[i%][j-]);
}
}
//cout << dp[n%2][n] << endl;
printf("%d\n", n-dp[n%][n]); } int main()
{
while(~scanf("%d", &n))
{
scanf("%s", s1+); for(int i = ; i < n; i++)
s2[i+] = s1[n-i]; LCS(); }
return ;
}

														
		

POJ 1159 - Palindrome (LCS, 滚动数组)的更多相关文章

  1. poj - 1159 - Palindrome(滚动数组dp)

    题意:一个长为N的字符串( 3 <= N <= 5000).问最少插入多少个字符使其变成回文串. 题目链接:http://poj.org/problem?id=1159 -->&gt ...

  2. POJ 1159 Palindrome&lpar;区间DP&sol;最长公共子序列&plus;滚动数组&rpar;

    Palindrome Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 56150   Accepted: 19398 Desc ...

  3. POJ 1159 Palindrome&lpar;字符串变回文&colon;LCS&rpar;

    POJ 1159 Palindrome(字符串变回文:LCS) id=1159">http://poj.org/problem? id=1159 题意: 给你一个字符串, 问你做少须要 ...

  4. poj 1159 Palindrome 【LCS】

    任意门:http://poj.org/problem?id=1159 解题思路: LCS + 滚动数组 AC code: #include <cstdio> #include <io ...

  5. hdu 1513 &amp&semi;&amp&semi; 1159 poj Palindrome &lpar;dp&comma; 滚动数组, LCS&rpar;

    题目 以前做过的一道题, 今天又加了一种方法 整理了一下..... 题意:给出一个字符串,问要将这个字符串变成回文串要添加最少几个字符. 方法一: 将该字符串与其反转求一次LCS,然后所求就是n减去 ...

  6. LCS&lpar;滚动数组&rpar; POJ 1159 Palindrome

    题目传送门 题意:一个字符串要变成回文串至少要插入多少个字符 分析:LCS,长度 - 原串和反串的最大相同长度就是要插入的个数.解释一下,当和反串相同时,在原串中已经是回文的部分了,那么减去LCS长度 ...

  7. HDU 1513 &amp&semi;&amp&semi; POJ 1159 Palindrome &lpar;DP&plus;LCS&plus;滚动数组&rpar;

    题意:给定一个字符串,让你把它变成回文串,求添加最少的字符数. 析:动态规划是很明显的,就是没有了现思路,还是问的别人才知道,哦,原来要么写,既然是回文串, 那么最后正反都得是一样的,所以我们就正反求 ...

  8. 动态规划&plus;滚动数组 -- POJ 1159 Palindrome

    给一字符串,问最少加几个字符能够让它成为回文串. 比方 Ab3bd 最少须要两个字符能够成为回文串 dAb3bAd 思路: 动态规划 DP[i][j] 意味着从 i 到 j 这段字符变为回文串最少要几 ...

  9. POJ 1159 回文LCS滚动数组优化

    详细解题报告可以看这个PPT 这题如果是直接开int 5000 * 5000  的空间肯定会MLE,优化方法是采用滚动数组. 原LCS转移方程 : dp[i][j] = dp[i - 1][j] + ...

随机推荐

  1. Raytracer

    http://www.cnblogs.com/miloyip/archive/2010/03/29/1698953.html http://www.scratchapixel.com/lessons/ ...

  2. 浅谈python中得import xxx,from xxx import xxx, from xxx import &ast;

    在python中import跟from import都是用来导入的,但是导入的机制不同 1.import xxx:导入模块,或者文件夹,对于调用模块或者文件夹中子模块的变量或者函数,需要使用&quot ...

  3. uboot总结:uboot配置和启动过程3(config&period;mk分析)

    说明:文件位置:在uboot的目录下,文件名为:config.mk.是一个makefile文件,以后会被主Makefile调用. 它的主要作用的是: (1)具体的设置交叉编译工具链接(主Makefil ...

  4. HDU 4869 Turn the pokers&lpar;推理&rpar;

    HDU 4869 Turn the pokers 题目链接 题意:给定n个翻转扑克方式,每次方式相应能够选择当中xi张进行翻转.一共同拥有m张牌.问最后翻转之后的情况数 思路:对于每一些翻转,假设能确 ...

  5. 关于IOS的Cocoapods相关问题

    Cocoa Pods确实是一个方便的工具,特别是在敏捷开发多个项目的时候,一个工具重复使用,大量节约时间: 可以及时更新github上面的开源库代码,只要改动Podfile文件中对应的开源库的版本号即 ...

  6. CodeForces 614A Link&sol;Cut Tree

    #include<cstdio> #include<cstring> #include<cmath> #include<stack> #include& ...

  7. 阅读:ECMAScript 6 入门&lpar;1&rpar;

    参考 ECMAScript 6 入门 ES6新特性概览 ES6 全套教程 ECMAScript6 (原著:阮一峰) JavaScript 教程 重新介绍 JavaScript(JS 教程) 前言 学了 ...

  8. JS中DOM以及BOM

    一.bom对象 1screen对象 console.log(screen.width);// 屏幕宽度 console.log(screen.height);// 屏幕高度 console.log(s ...

  9. Matlab绘图添加直角坐标轴

    绘制y=x^2,并添加直角坐标轴. clear;clc;close all %% 绘制方程 x = -10:0.01:10; figure; y = x.^2-30; plot(x,y,'k','li ...

  10. Java——基本概念

    body, table{font-family: 微软雅黑; font-size: 10pt} table{border-collapse: collapse; border: solid gray; ...