HDU 2476 String painter 區間dp

題意: 給出兩個字元串, 定義操作為将a串任意連續區間改為相同的一個字元, 問最少多少次操作可以讓a變為b.

思路:

直接做太難了. 看了kuangbin的部落格才知道可以這樣做.

先用區間dp搞定從空白串變為b串所需要的操作次數.

至于a串變b串, 要用到ans數組記錄前j位的最小操作數.

a[i]若與b[i]相同, 那麼ans[i]就可以用ans[i-1]更新.

求讓前i位變身的最小操作數需要枚舉ans和dp分界位置, 找到最小的ans[i].

#include<bits/stdc++.h>

using namespace std;

const int M = 105;
const int inf = 1e9 + 5;

char a[M], b[M];
int dp[M][M];
int n;

void init() {
    fill(dp[0], dp[0] + M * M, inf);
}

void solve() {
    for (int len = 1; len <= n; len++) {
        for (int s = 0; s + len - 1 < n; s++) {
            int t = s + len - 1;
            if (s == t) {
                dp[s][t] = 1;
                continue;
            }
            int tmp = len;
            if (b[s] == b[s + 1]) {
                tmp = min(tmp, dp[s + 1][t]);
            }
            if(len>=3&&b[s]==b[t]){
                tmp=min(tmp,dp[s+1][t]);
            }
            for (int k = s; k + 1 <= t; ++k) {
                tmp = min(tmp, dp[s][k] + dp[k + 1][t]);
            }
            dp[s][t] = tmp;
        }
    }
    
    int ans[M];
    for (int i = 0; i < n; i++) {
        ans[i] = dp[0][i];
        if (a[i] == b[i]) {
            if (i == 0)ans[i] = 0;
            else ans[i] = ans[i - 1];
        } else
            for (int j = 0; j < i; j++) {
                ans[i] = min(ans[i], ans[j] + dp[j+1][i]);
            }
    }

/*

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; ++j) {
            printf("[%d,%d]:%d ",i,j, dp[i][j]==inf?999:dp[i][j]);
        }
        puts("");
    }
*/

/*

    for (int i = 0; i < n; ++i) {
        printf("%d ", ans[i]);
    }
*/
    printf("%d\n",ans[n-1]);
}

int main() {
    while (~scanf("%s%s", a, b)) {
        init();
        n = strlen(a);
        solve();
    }
    return 0;
}
           

TP