HDU. 2476 String painter

发表于 更新于 分类于

链接

http://acm.hdu.edu.cn/showproblem.php?pid=2476

题意

有两个长度相等的字符串 $A$ 和 $B$，你可以把字符串中连续的一段区间修改成一个相同的字符，现在你要把字符串 $A$ 变成 $B$，最少要修改多少次？

思路

将 $A$ 修改成 $B$ 相对于将空串修改成 $B$ 唯一不同的是可能存在 $A_{i\sim j} =B_{i \sim j}$，那么这段区间可以不操作，但是不保证总操作数最小。

因此先计算将空串修改成字符串 $B$ 的最少次数，定义 $dp_{l,r}$ 为将空串修改成 $B_{l \sim r}$ 的最少次数：

  • 当 $B_i=B_j$ 时，$dp_{i,j}=dp_{i+1,j}=dp_{i,j-1}$；
  • 当 $B_i\neq B_j$ 时，$dp_{i,j}=\min{dp_{i,k}+dp_{k+1,j}}$ $(i \le k < j)$。

接下来考虑将 $A$ 修改成 $B$，定义 $f_{i}$ 为将 $A_{0 \sim i}$ 修改成 $B_{0 \sim i}$ 的最少次数：

  • 当 $A_i=B_i$ 时，$f_i=min(dp_{0,i},f_{i-1})$；
  • 当 $A_i\neq B_i$ 时，$f_i=\min(dp_{0,i},\min{f_j+dp_{j+1,i}})$ $(0 \le j < i)$。

代码

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
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
int dp[105][105],f[105];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a,b;
    while(cin>>a>>b) {
        int n=SZ(a);
        memset(dp,0x3f,sizeof dp);
        for(int i=0;i<n;i++) dp[i][i]=1;
        for(int len=2;len<=n;len++)
            for(int l=0;l+len-1<n;l++) {
                int r=l+len-1;
                if(b[l]==b[r]) dp[l][r]=dp[l+1][r];
                else for(int k=l;k<r;k++) dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
            }
        f[0]=a[0]!=b[0];
        for(int i=1;i<n;i++) {
            if(a[i]==b[i]) f[i]=f[i-1];
            else {
                f[i]=dp[0][i];
                for(int j=0;j<i;j++) f[i]=min(f[i],f[j]+dp[j+1][i]);
            }
        }
        cout<<f[n-1]<<'\n';
    }
    return 0;
}