- 浏览: 196938 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
题目大意:给你一段字符串,让你求出在中间最少加入几个字符可以让他变成一段回文子串。
解题思路:假设S是一段字符串,S'是S的逆串,则只需求出S与S'的最长公共子序列即可的长度即可,最后用字符串的长度减去最长公共子序列的长度即是这道题目所求的加入的字母的长度。转化为LCS问题即可
注意:本题的内存开销非常大,由于题目中给出0<=N<=5000,
1. 静态数组 开销大小为5001*5001的int是铁定超的.据说用short int的话不会MLE,有兴趣的同学可以试试
2.动态数组 单纯的申请动态数组是不能解决这个问题的,动态数组只能增加空间利用率,但是本题最恶劣的数组大小还是5001*5001,动态数组是不能改变这个事实的
3. 滚动数组 这里重点讲一下滚动数组在这个题目中的应用.自己目前理解的应用滚动数组的目的就是减少空间开销.首先可以在纸上简单模拟一下DP的转移过程.确定好最少行数或者列数之后,重点就是在如何进行"滚动"以及如何用表达式控制这个滚动.
对于本题,我用的是行数以0--1--0—1的滚动方式,滚动表达式为i%2和(i-1)%2 ,没错,就是强大的求余滚动O(∩_∩)O
而且本题我为了稍微提高一点空间利用率,使用了 动态二维滚动数组,就是东邪(动态)西毒(滚动)的混合体O(∩_∩)O,这样做的目的,只是对测试数据库的数据抱有一点点希望:我相信它们不全都是5000的长度,所以我想能尽可能再节省一点列数….不过时间就惨不忍睹咯,1157ms….不过空间开销却由MLE跌落到谷底的280K\(^o^)/~
本题代码如下:
//Memory Time //280K 1157MS #include<iostream> using namespace std; int max(int a,int b) { return a>b?a:b; } int main(int i,int j) { int n; while(cin>>n) { /*Input*/ char* s1=new char[n+1]; char* s2=new char[n+1]; //s1的逆序列 int **dp=new int*[n+1]; //定义二维动态滚动数组(本题以01行滚动) dp[0]=new int[n+1]; dp[1]=new int[n+1]; dp[0][0]=dp[1][0]=0; //动态数组初始化 行开头为全0 for(i=1,j=n;i<=n;i++,j--) { dp[0][i]=dp[1][i]=0; //动态数组初始化 列开头为全0 char temp; cin>>temp; s1[i]=s2[j]=temp; } /*Dp-LCS*/ int max_len=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(s1[i]==s2[j]) dp[i%2][j]=dp[(i-1)%2][j-1]+1; //如果字符相等,则继承前一行前一列的dp值+1 else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]); //否则,取上方或左方的最大dp值 if(max_len<dp[i%2][j]) max_len=dp[i%2][j]; } cout<<n-max_len<<endl; delete s1; delete s2; delete[] dp; } return 0; }
附件图片中为一般的LCS算法,图片中的两个序列分别为x={2,5,7,9,3,1,2}与y={3,5,3,2,8}
这个解题报告很多是来自http://blog.csdn.net/lyy289065406/article/details/6648163
大家可以去围观下这位大神的解题报告。
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 789虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 787选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 813题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 949题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 935字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 3176
2012-05-28 14:47 977大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1573题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2673是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1207在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 777从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2352题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1063题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1227大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 949大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 964题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2118大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1226题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 896题意:Ted今年100岁,给出n对他家族的关系:“父 ... -
poj 1656
2012-04-19 10:07 1095题目要求:一道纯的模拟题目。 直接上代码: ...
相关推荐
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1159-Palindrome
NULL 博文链接:https://128kj.iteye.com/blog/1757060
1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索...
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
pku online judge 通过源码 C/C++
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
palindrome
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1011 1012 1013 1014 ...1159 1160 1163 1164 1166 1174 1177 1182 1183 1186 1188 1189 1190 1191 1195 1200 1201 1207 1218 1226 1251 1256 1258 1260 1273 1274 ...
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1011 1012 1013 1014 ...1159 1163 1164 1166 1182 1188 1189 1190 1207 1218 1256 1258 1273 1298 1305 1308 1319 1321 1323 1328 1339 1401 1422 1455 1458 1477 ...