String painter: DP

· · 题解

UVA1437 String painter

题目描述

有两个仅含有小写字母的等长字符串 A 和 B，每次操作可以将 A 的其中一个子串的所有位置修改为同一个任意字符。求将 A 覆盖成 B 的最小操作次数。

1\le |a |=|b|\le100。

输入格式

输入包含多组数据，每组数据由两行组成，第一行为字符串 A，第二行为字符串 B。

输出格式

对于每组数据，输出最小操作次数。

题解

问题分析

也是一道紫题啊家人们。

要将字符串 A 转换为 B，每次操作可以覆盖一个子串为同一字符。最小操作次数取决于：

1.B 的字符分布（如连续相同字符可被一次性覆盖）。

2.A 和 B 的初始匹配位置（已匹配的位置无需操作）。

关键观察

1.覆盖操作独立于 A 的初始状态（可设置任意字符），因此子串 [i..j] 的最小操作次数仅由 B[i..j] 决定。

2.但整体转换时，A 的初始匹配位置可减少操作（例如，如果 A[i]=B[i] 且未被覆盖，则无需额外操作）。

动态规划

1.定义

dp[i][j]：将任意字符串转换为 B[i..j] 的最小操作次数（区间 DP，基于 B）。

ans[i]：将 A[1..i] 转换为 B[1..i] 的最小操作次数（前缀 DP，利用 A）。

2.状态转移

(1)dp[i][j] 转移（枚举区间长度 l=j-i+1):

基础

l=1 时，dp[i][i] = 1（覆盖单个字符）。

递归

① 如果 B[i]=B[j]，则 dp[i][j] = min(dp[i+1][j], dp[i][j-1])。

端点字符相同，覆盖整个子串的操作可能被优化（例如，通过扩展相邻区间的操作）。

② 否则，枚举分割点 k，将区间分为 [i..k] 和 [k+1..j] 独立处理：计算 dp[i][k] + dp[k+1][j] 最小值。

直接上代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
char a[105],b[105];
int n,dp[105][105],ans[105];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    while(cin>>a+1>>b+1){
        n=strlen(a+1);
        memset(dp,100,sizeof(dp));
        memset(ans,100,sizeof(ans));
        ans[0]=0;
        for(int i=1;i<=n;i++) dp[i][i]=1;
        for(int l=2;l<=n;l++)
            for(int i=1;i+l-1<=n;i++){
                int j=i+l-1;
                if(b[i]==b[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
                else for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        for(int i=1;i<=n;i++){
            if(a[i]==b[i]) ans[i]=ans[i-1];
            else for(int k=0;k<i;k++) ans[i]=min(ans[i],ans[k]+dp[k+1][i]);
        }
        cout<<ans[n]<<endl;
    }
    return 0;
}