2025-ICPC-Asia-Taiwan-Online-台湾网络赛-D. Palindromic Distance（字符串与回文串之间的最短距离）（不要那么死板，dp 的转移顺序是可以变的）

题目大意

两个字符串$u$和$v$之间的编辑距离是将$u$转换为$v$的最小编辑操作次数。可以对字符串应用三种编辑操作：插入字符，删除字符，用不同字符替换某个字符。

例如，我们可以用四次替换将hello转换为world，因此编辑距离最多为$4$。您可以用两次替换和一次插入将wally转换为walter，因此编辑距离最多为$3$。计算两个字符串之间的编辑距离是一个众所周知的问题，有许多应用。

当前任务是计算一个字符串到最接近的回文串的编辑距离。回文串是从后往前读和从前往后读相同的字符串，例如madam。

hello到最接近回文串的编辑距离仅为$2$：我们可以用两次编辑操作将hello转换为ollo，或hllh，或elle。

编写一个程序，可以找到一个单词到最接近回文串的距离。

思路讲解

auto dfs=[&](auto && self,ll l,ll r) -> ll {
    if (r==l) {
        return 0;
    }
    if (r-l==1) {
        return s[l]!=s[r];
    }
    if (dp[l][r]!=INF) {
        return dp[l][r];
    }
    dp[l][r]=min({self(self,l+1,r-1)+(s[l]!=s[r]),      // 替换
        self(self,l,r-1)+1,     // 删除右侧（等价于左侧插入一个相同的抵消）
        self(self,l+1,r)+1,     // 删除左侧（等价于在右侧插入一个相同的）
    });
    return dp[l][r];
};

AC代码

AC
https://codeforces.com/gym/106084/submission/361098919

源代码

/**
 * Problem: D. Palindromic Distance
 * Contest: 2025 ICPC Asia Taiwan Online Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106084/problem/D
 * Created: 2026-02-02 14:13:18
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
bool check(const string &s) {
    ll sz=s.size();
    for (int i=0;i<sz;++i) {
        if (s[i]!=s[sz-i-1]) {
            return false;
        }
    }
    return true;
}
void Solve() {
    string s;
    cin>>s;
    if (check(s)) {
        cout<<0<<"\n";
        return;
    }
    ll N=s.size();
    s.insert(s.begin(),'#');
    vector dp(N+2,vector<ll>(N+2,INF));
    auto dfs=[&](auto && self,ll l,ll r) -> ll {
#ifdef LOCAL
        assert(r>=l);
#endif
        if (r==l) {
            return 0;
        }
        if (r-l==1) {
            return s[l]!=s[r];
        }
        if (dp[l][r]!=INF) {
            return dp[l][r];
        }
        dp[l][r]=min({self(self,l+1,r-1)+(s[l]!=s[r]),
            self(self,l,r-1)+1,
            self(self,l+1,r)+1,
        });
        return dp[l][r];
    };
    ll ans=dfs(dfs,1,N);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106084/submission/361098919

*/

心路历程（WA，TLE，MLE……）