51NOD 1092 回文字符串 LCS

Q：给定一个串，问需要插入多少字符才能使其成为回文串，也就是左右对称的串。

经典求LCS题，即最长公共子序列，不用连续的序列。考虑O(n²)解法，求LCS起码得有两个串，题中才给了一个串，另一个需要自己造，将给定的串反置，然后求这两个串的LCS。假设两个串为str1和str2，想办法将规模降低，分两种情况考虑：

str1[i]==str2[j]，则dp[i][j] = dp[i-1][j-1] + 1，其中dp[i][j]表示str1[1_i]与str2[1j]的最长公共子序列长度。
str1[i]!=str2[j]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

这其实就是用小规模来推出稍大规模的解，也就是DP思想了。所求得的LCS就是最长回文子序列的长度了，没有包含在LCS中的字符都是需要为它们插入一份拷贝的。答案自然就是size-lcs。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int dp[N][N];

char str[N], cpy[N];

int MaxMirrorSeq(char *sp, int size)

{

    memcpy(cpy, sp, size+2);

    reverse(cpy+1, cpy+1+size); //反置

    memset(dp, 0, sizeof(dp));

    int ans = 0;

    for(int i=1; i<=size; i++)

    {

        for(int j=1; j<=size; j++)

        {

            if(str[i]==cpy[j]) dp[i][j] = dp[i-1][j-1]+1;

            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

            ans = max(ans, dp[i][j]);

        }

    }

    return ans;

}

int main()

{

    freopen("input.txt", "r", stdin);

    while(~scanf("%s", str+1)) {

        int size = strlen(str+1);

        cout<<size-MaxMirrorSeq(str, size)<<endl;

    }

    return 0;

}

巴特西

51NOD 1092 回文字符串 LCS

Q：给定一个串，问需要插入多少字符才能使其成为回文串，也就是左右对称的串。

最新文章

热门文章