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;
}