HDU2476 String painter(DP)

題目

String painter
給出兩個字元串s1,s2。對於每次操作可以將 s1 串中的任意一個子段變成另一個字元。問最少需要多少步操作能將s1串變為s2串。

解析

太妙了這個題，mark一下。

這個題先考慮怎麼由空串轉化s2，
\(f[i][j]\)表示從空串到s2最少的次數，
則有\(f[i][j]=s[i+1][j]+1\)，
若\([i+1,j]\)存在一個\(k\)，使\(s2[i]==s2[k]\)，則\(f[i][j]=min\{f[i+1][k]+f[k+1][j]\}\)，
\(k\)為斷點，\(i\)和\(k\)同時刷。

然後再考慮把s1刷成s2的代價
設\(sum[i]\)表示把\(s1[1,i]\)刷成\(s2[1,i]\)的次數
當\(s1[i]==s2[i]\)時，可以不刷，顯然\(sum[i]=sum[i-1]\)
否則，在區間內找最小次數\(sum[i]=min\{sum[j]+f[j+1][i]\}\)

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

int n, m;

int f[N][N], sum[N];

char s[N], t[N];

int main() {
    while (cin >> s) {
        cin >> t;
        memset(f, 0, sizeof f);
        memset(sum, 0, sizeof sum);
        int len = strlen(s);
        for (int i = 0; i < len; ++i) f[i][i] = 1;
        for (int i = 0; i < len; ++i) 
            for (int j = i - 1; j >= 0; --j) {
                f[j][i] = f[j + 1][i] + 1;
                for (int k = j + 1; k <= i; ++k) if (t[j] == t[k])
                    f[j][i] = min(f[j][i], f[j + 1][k] + f[k + 1][i]);
            }
        for (int i = 0; i < len; ++i) sum[i] = f[0][i];
        if (s[0] == t[0]) sum[0] = 0;
        for (int i = 1; i < len; ++i) {
            if (s[i] == t[i]) sum[i] = min(sum[i], sum[i - 1]);
            else for (int j = 0; j < i; ++j) sum[i] = min(sum[i], sum[j] + f[j + 1][i]);
        }
        cout << sum[len - 1] << endl;
    }
}