【动态规划】【poj 1159】palindrome

问题

给定一个长度为n（<=5000）的字符串，求最少添加几个字符使之变成回文串

分析

设原序列S的逆序列为S'，则这道题目的关键在于，

最少需要补充的字母数= 原序列S的长度— S和S'的最长公共子串长度

设 S 为原字符串，RS=reverse(S)即S反转后的字符串，LCS(S,RS)为S与RS的最长公共子序列，len(S)为S的长度。令S={a1~an},则RS={an~a1}，S-LCS(S,RS)={b1~bn}，这里的集合都是有序、元素可重复的；bi∈S,RS；且i≠j时，bi≠bj，否则有bi∈LCS(S,RS)；同时LCS(S,RS)一定是回文，因为其是在S的正序与逆序下同时出现的子序列。由上，只需添加字符将S-LCS(S,RS)变成回文即可，设size=len(S-LCS(S,RS))；因为其元素各不相同，此时有两种方案使之成为回文：1.添加size-1个字符，例如:c1c2c3
--> c1c2c3c2c1；2.添加size个；对于第一种，c3肯定是在回文中的中间位置，也必须是在LCS(S,RS)的中间位置，即c3∈LCS(S,RS)，所以排除这种情况。于是最少需添加size个字符，即min=len(S)-len(S,RS)。

这个证明需要自己思考一下。

这道题由于空间需求很大，所以考虑用滚动数组优化。

由于i之和i中已更新的和i-1有关，所以只需2*5000就能解决问题，但是会使算法的时间复杂度接近n3，以时间换空间，所谓的求余滚动效率并不高，因为mod运算非常之慢。

code

View Code?

program
liukeke;

var

f:array[0..1,0..5001]
of longint;

n,i,j:longint;

s1,s2:ansistring;

function
max(a,b:longint):longint;

begin

if
a>b then
exit(a);

exit(b);

end;

begin

readln(n);

readln(s1);

for
i:=1
to length(s1) do

s2:=s1[i]+s2;

for
i:=1
to length(s1) do

begin

for
j:=1
to length(s2) do

if
s1[i]=s2[j] then

f[1,j]:=f[0,j-1]+1

else

f[1,j]:=max(f[0,j],f[1,j-1]);

f[0]:=f[1];

end;

writeln(length(s1)-f[1,length(s2)]);

end.

反思

要看清题目，不要一味套用经典算法，通过分析使之和经典算法建立联系。

考虑优化

 

POJ1159-Palindrome

分类： POJ解题报告2011-07-31
12:18 1697人阅读 评论(0) 收藏 举报

delete数据库input算法测试

 

转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1300587979 

设原序列S的逆序列为S' ，则这道题目的关键在于，

最少需要补充的字母数 = 原序列S的长度 —  S和S'的最长公共子串长度
这个公式我不证明，不难证
剩下的就小意思了，最基础的LCS题。

注意本题空间开销非常大，需要适当的处理手法

 

先看看几种不同的申请空间方法的区别：

1. 静态数组 开销大小为5001*5001的int是铁定超的.

据说用short int的话不会MLE，有兴趣的同学可以试试

2. 动态数组 单纯的申请动态数组是不能解决这个问题的，动态数组只能增加空间利用率，

            但是本题最恶劣的数组大小还是5001*5001，动态数组是不能改变这个事实的

3. 滚动数组 这里重点讲一下滚动数组在这个题目中的应用.自己目前理解的应用滚动数组的目的就是减少空间开销.首先可以在纸上简单模拟一下DP的转移过程.确定好最少行数或者列数之后,重点就是在如何进行"滚动"以及如何用表达式控制这个滚动.

对于本题,我用的是行数以0--1--0—1的滚动方式，滚动表达式为i%2和(i-1)%2 ，没错，就是强大的求余滚动O(∩_∩)O 

由于应用了滚动数组，那么空间开销就能够从5001*5001压缩到 2*5001  ！！！

哈哈，傻眼了吧\(^o^)/~

而且本题我为了稍微提高一点空间利用率，使用了 动态二维滚动数组，就是东邪（动态）西毒（滚动）的混合体O(∩_∩)O，这样做的目的，只是对测试数据库的数据抱有一点点希望：我相信它们不全都是5000的长度，所以我想能尽可能再节省一点列数….不过时间就惨不忍睹咯,1157ms….不过空间开销却由MLE跌落到谷底的280K\(^o^)/~

跪求传说中 300K 16ms代码………….

 

顺便贴一下LCS的图解算法

 

s1：2 5 7 9 3 1 2

s2：3 5 3 2 8

一.   使用二維陣列

二.   記錄每一格的結果，是由哪一格而來

1.       陣列開頭均設為空

2.       S1[i]=S2[j]相同，dp[i][j]则继承左上方向dp[i-1][j-1]的值+1

3.       不相同dp[i][j]则继承 上方與左方中的最大數值

最后整个二維陣列中最大的值，就是s1和s2的最长公共子串长度

 

 

//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;
}