POJ 1159

最近发现做算法题最重要的是思路, 一开始的思路正确, 就会非常轻松的做出来, 反之, 会绕好长的路还不一定能出来…

这一题的关键是 最长公共子序列

我并没有想到… 然后呢, 在纸上模拟补齐, 嗯…

举个例子, Aba3bd和它的倒序db3abA, 它们的最长公共子序列是b3b, 所以只要最长的公共子序列对齐即可

A b a 3   b d
d b   3 a b A

只要对齐的字符越多, 要补的字符就越少

然后中间空出来的部分, 照抄上面的或者下面的
两边不同的部分, 直接错开对齐就行

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

int main() {
    int n;
    cin >> n;
    string data;
    cin >> data;
    
    data = " " + data;
 
    static short dp[5050][5050];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (data[i] == data[n - j + 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    cout << n - dp[n][n] << endl;





    return 0;
}

滚动数组版

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

int main() {
    int n;
    cin >> n;
    string data;
    cin >> data;
    
    data = " " + data;

    int dp[2][5050];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (data[i] == data[n - j + 1]) {
                dp[i % 2][j] = dp[(i+1) % 2][j - 1] + 1;
            } else {
                dp[i % 2][j] = max(dp[i % 2][j - 1], dp[(i+1) % 2][j]);
            }
        }
    }

    cout << n - dp[n % 2][n] << endl;


    return 0;
}