Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 55018 | Accepted: 19024 |
Description
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
Output
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, 滚动数组)的更多相关文章
-
poj - 1159 - Palindrome(滚动数组dp)
题意:一个长为N的字符串( 3 <= N <= 5000).问最少插入多少个字符使其变成回文串. 题目链接:http://poj.org/problem?id=1159 -->> ...
-
POJ 1159 Palindrome(区间DP/最长公共子序列+滚动数组)
Palindrome Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 56150 Accepted: 19398 Desc ...
-
POJ 1159 Palindrome(字符串变回文:LCS)
POJ 1159 Palindrome(字符串变回文:LCS) id=1159">http://poj.org/problem? id=1159 题意: 给你一个字符串, 问你做少须要 ...
-
poj 1159 Palindrome 【LCS】
任意门:http://poj.org/problem?id=1159 解题思路: LCS + 滚动数组 AC code: #include <cstdio> #include <io ...
-
hdu 1513 &;&; 1159 poj Palindrome (dp, 滚动数组, LCS)
题目 以前做过的一道题, 今天又加了一种方法 整理了一下..... 题意:给出一个字符串,问要将这个字符串变成回文串要添加最少几个字符. 方法一: 将该字符串与其反转求一次LCS,然后所求就是n减去 ...
-
LCS(滚动数组) POJ 1159 Palindrome
题目传送门 题意:一个字符串要变成回文串至少要插入多少个字符 分析:LCS,长度 - 原串和反串的最大相同长度就是要插入的个数.解释一下,当和反串相同时,在原串中已经是回文的部分了,那么减去LCS长度 ...
-
HDU 1513 &;&; POJ 1159 Palindrome (DP+LCS+滚动数组)
题意:给定一个字符串,让你把它变成回文串,求添加最少的字符数. 析:动态规划是很明显的,就是没有了现思路,还是问的别人才知道,哦,原来要么写,既然是回文串, 那么最后正反都得是一样的,所以我们就正反求 ...
-
动态规划+滚动数组 -- POJ 1159 Palindrome
给一字符串,问最少加几个字符能够让它成为回文串. 比方 Ab3bd 最少须要两个字符能够成为回文串 dAb3bAd 思路: 动态规划 DP[i][j] 意味着从 i 到 j 这段字符变为回文串最少要几 ...
-
POJ 1159 回文LCS滚动数组优化
详细解题报告可以看这个PPT 这题如果是直接开int 5000 * 5000 的空间肯定会MLE,优化方法是采用滚动数组. 原LCS转移方程 : dp[i][j] = dp[i - 1][j] + ...
随机推荐
-
Raytracer
http://www.cnblogs.com/miloyip/archive/2010/03/29/1698953.html http://www.scratchapixel.com/lessons/ ...
-
浅谈python中得import xxx,from xxx import xxx, from xxx import *
在python中import跟from import都是用来导入的,但是导入的机制不同 1.import xxx:导入模块,或者文件夹,对于调用模块或者文件夹中子模块的变量或者函数,需要使用" ...
-
uboot总结:uboot配置和启动过程3(config.mk分析)
说明:文件位置:在uboot的目录下,文件名为:config.mk.是一个makefile文件,以后会被主Makefile调用. 它的主要作用的是: (1)具体的设置交叉编译工具链接(主Makefil ...
-
HDU 4869 Turn the pokers(推理)
HDU 4869 Turn the pokers 题目链接 题意:给定n个翻转扑克方式,每次方式相应能够选择当中xi张进行翻转.一共同拥有m张牌.问最后翻转之后的情况数 思路:对于每一些翻转,假设能确 ...
-
关于IOS的Cocoapods相关问题
Cocoa Pods确实是一个方便的工具,特别是在敏捷开发多个项目的时候,一个工具重复使用,大量节约时间: 可以及时更新github上面的开源库代码,只要改动Podfile文件中对应的开源库的版本号即 ...
-
CodeForces 614A Link/Cut Tree
#include<cstdio> #include<cstring> #include<cmath> #include<stack> #include& ...
-
阅读:ECMAScript 6 入门(1)
参考 ECMAScript 6 入门 ES6新特性概览 ES6 全套教程 ECMAScript6 (原著:阮一峰) JavaScript 教程 重新介绍 JavaScript(JS 教程) 前言 学了 ...
-
JS中DOM以及BOM
一.bom对象 1screen对象 console.log(screen.width);// 屏幕宽度 console.log(screen.height);// 屏幕高度 console.log(s ...
-
Matlab绘图添加直角坐标轴
绘制y=x^2,并添加直角坐标轴. clear;clc;close all %% 绘制方程 x = -10:0.01:10; figure; y = x.^2-30; plot(x,y,'k','li ...
-
Java——基本概念
body, table{font-family: 微软雅黑; font-size: 10pt} table{border-collapse: collapse; border: solid gray; ...