Codeforces Beta Round #52 (Div. 2) D. Changing a String DP输出方案

https://codeforces.com/contest/56/problem/D

• 就是编辑距离的加强版，需要输出方案，那么状态转移方程应该比较常规了，设$dp[i][j]$表示$s$的前$i$个字符变成$t$的前$j$个字符所需要的最少操作次数，那么$dp[i][0],dp[0][j],dp[0][0]$作为初始状态，容易列出状态转移方程为 d p [ i ] [ j ] = m i n { d p [ i ? 1 ] [ j ] , d p [ i ? 1 ] [ j ? 1 ] , d p [ i ] [ j ? 1 ] } + 1 , ( s [ i ] = t [ j ] ) d p [ i ] [ j ] = d p [ i ? 1 ] [ j ? 1 ] , ( s [ i ] ≠ t [ j ] ) dp[i][j]=min\{dp[i-1][j],dp[i-1][j-1],dp[i][j-1]\}+1,(s[i]=t[j])\\dp[i][j]=dp[i-1][j-1],(s[i]\neq t[j]) dp[i][j]=min{ dp[i?1][j],dp[i?1][j?1],dp[i][j?1]}+1,(s[i]=t[j])dp[i][j]=dp[i?1][j?1],(s[i]??=t[j])
• 重点说一下怎么输出方案，其实就是背包的输出方式，倒序输出，看$dp[i][j]$是从哪个状态转移过来的，比方说从$dp[i?1][j]$转移过来，那么这一次所做的操作实际上是删除字符，因为$s$的前$i?1$个字符和$t$的前$j$个字符已经匹配，那么只能把第$i$个字符删掉，这样才能保证对于$t$的前$j$个字符能够完成匹配

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int INF = 0x3f3f3f3f;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s, t;cin >> s;cin >> t;int n = s.length();int m = t.length();vector<vector<int> > dp(n + 1, vector<int>(m + 1));for(int i=1;i<=n;i++) dp[i][0] = i;for(int j=1;j<=m;j++) dp[0][j] = j;dp[0][0] = 0;for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    if(s[i - 1] != t[j - 1]) dp[i][j] = min({
    dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]}) + 1;else dp[i][j] = dp[i - 1][j - 1];}}cout << dp[n][m] << '\n';while(n > 0 || m > 0){
    if(m > 0 && n > 0 && dp[n][m] == dp[n - 1][m - 1] + 1){
    // 替换cout << "REPLACE" << ' ' << n << ' ' << t[m - 1] << '\n';n -= 1;m -= 1;continue;}if(m > 0 && dp[n][m] == dp[n][m - 1] + 1){
    // 插入,相当于s的前n个字符和t的前m-1个字符匹配,需要插入一个字符到s的第n个位置 才能和t的前m个字符匹配cout << "INSERT" << ' ' << n + 1 << ' ' << t[m - 1] << '\n';// 这里n从0开始m -= 1;continue;}if(n > 0 && dp[n][m] == dp[n - 1][m] + 1){
    cout << "DELETE" << ' ' << n << '\n';n -= 1;continue;}n -= 1;m -= 1;}return 0;
}