UVA1437 String painter 题解

题目链接：UVA1437 String painter

题意：There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?

1 <= |A|=|B| <= 100

显然区间dp

考虑A与B完全不同时

设 $f[i][j]$ 表示暴力（不管A的情况）修改 $[i,j]$ 的最小花费

那就是这个题目了

当 $i=j$ 时，有

$$f[i][j]=1$$

当 $i\ne j$ 时，

• 若 $b[i]=b[j]$ ，此时只需要 $[i+1,j]$ 或 $[i,j-1]$ 首次涂的时候多涂一格即可

  $$f[i][j]=\min(f[i+1][j],f[i][j-1])$$

• 若 $b[i]\ne b[j]$ ， $b[i],b[j]$ 都可以尝试向内扩展，显然 $[i,j]$ 首次涂会涂两种颜色，考虑枚举其断点 $k$

  $$f[i][j]=\min(f[i][j],f[i][k]+f[k+1][j])$$

显然有时候我们的暴力修改时不必要的

设 $g[i]$ 表示 $[1,i]$ 的最小修改，则 $g[i]$ 至多为 $f[1][i]$ ，且有 $g[0]=0$

• 若 $a[i]=b[i]$ ，则

  $$g[i]=g[i-1]$$

  显然这个 $g[i-1]$ 一定不大于 $f[1][i]$ ，直接转移即可

• 若 $a[i] \ne b[i]$ ，则此时 $a[i]$ 是必须得暴力修改的了

  但是这个修改长度我们不知道

  考虑枚举一个断点 $k$ ，也就是 $[k+1,i]$ 第一次涂色涂成 $a[i]$

  为什么不是上个极大公共子串的末尾开始呢？

  考虑这种情况

  zzzzfzzzz
  abcdfdcba

  最小花费为 $5$

  故转移方程为

  $$g[i]=\min_{0 \le k \le i}(g[i],g[k]+f[k+1][i])$$

时间复杂度 $O(Qn^2)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(105)

char a[N],b[N];
int n,f[N][N],g[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> (a+1) >> (b+1))
    {
        n=strlen(a+1);
        memset(f,0x3f,sizeof(f));
        memset(g,0x3f,sizeof(g));
        for(int i=1; i<=n; i++)f[i][i]=1;
        for(int len=2; len<=n; len++)
            for(int i=1,j=i+len-1; j<=n; i++,j++)
            {
                if(b[i]==b[j])
                    f[i][j]=min(f[i+1][j],f[i][j-1]);
                else for(int k=i; k<j; k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
        g[0]=0;
        for(int i=1; i<=n; i++)
        {
            if(a[i]==b[i])g[i]=g[i-1];
            else for(int k=0; k<i; k++)
                g[i]=min(g[i],g[k]+f[k+1][i]);
        }
        cout << g[n] << '\n';
    }
    return 0;
}