Saturday, March 23, 2019

POJ-1159 将字符串变成至回文串

admin    March 23, 2019    No comments



POJ 1159

最近发现做算法题最重要的是思路, 一开始的思路正确, 就会非常轻松的做出来, 反之, 会绕好长的路还不一定能出来…
这一题的关键是 最长公共子序列
我并没有想到… 然后呢, 在纸上模拟补齐, 嗯…
举个例子, Aba3bd和它的倒序db3abA, 它们的最长公共子序列是b3b, 所以只要最长的公共子序列对齐即可



1
2
A b a 3   b d
d b   3 a b A
只要对齐的字符越多, 要补的字符就越少
然后中间空出来的部分, 照抄上面的或者下面的
两边不同的部分, 直接错开对齐就行



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}
滚动数组版



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)