最长公共子序列, POJ1159

POJ1159

题意: 大致就是要求加入最少的字符, 使给的字符串成为回文串;

思路: 本来是关于回文的, 但是可以转化成对正反两个序列求最长公共子序列; 求得的最长公共子序列的长度就是原串中的本来的最长的回文串的长度 然后用总长度去减去最长的回文串的长度就是要使原串成为回文串 需要加入的最小的字符个数;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 5004;
// 直接开下面这个dp数组的话会超内存;
// 开int的是占 4*5004*5004 > 题目中的65536K;short is ok ;
// int dp[maxn][maxn];
short dp[maxn][maxn];
// int dp[maxn];
int n;
string s;

int main(){
    freopen("1159.in","r", stdin);
    scanf("%d", &n);
    cin>>s;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(s[i] == s[n-1-j]){
                dp[i+1][j+1] = dp[i][j] + 1;
            }
            else{
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
            }
        }
    }
    printf("%d \n", n - dp[n][n]);
    return 0;
}