P1435 回文字串【洛谷算法习题】

P1435 回文字串网页链接P1435 回文字串题目背景IOI2000 第一题题目描述回文词是一种对称的字符串。任意给定一个字符串通过插入若干字符都可以变成回文词。此题的任务是求出将给定字符串变成回文词所需要插入的最少字符数。比如Ab3bd \verb!Ab3bd!Ab3bd插入2 22个字符后可以变成回文词dAb3bAd \verb!dAb3bAd!dAb3bAd或Adb3bdA \verb!Adb3bdA!Adb3bdA但是插入少于2 22个的字符无法变成回文词。注意此问题区分大小写。输入格式输入共一行一个字符串。输出格式有且只有一个整数即最少插入字符数。输入输出样例 #1输入 #1Ab3bd输出 #12说明/提示数据范围及约定记字符串长度为l ll。对于全部数据0 l ≤ 1000 0l\le 10000l≤1000。解题思路本题是经典的回文构造问题核心通过问题等价转化将最少插入字符数求解转化为「原串与逆序串的最长公共子序列LCS」问题通过二维动态规划高效求解。问题等价性推导插入最少字符使字符串变为回文本质是尽可能保留原串中已有的对称字符结构回文字符串的正序与逆序完全一致因此原串中能构成回文的字符必然同时出现在原串和它的逆序串中且相对顺序保持一致。这部分最长的对称字符序列恰好等于原串与逆序串的最长公共子序列LCS。LCS长度越长需要补充的对称字符越少。最终结论最少插入字符数 字符串总长度 - 原串与逆序串的LCS长度。动态规划求解LCS状态定义dp[i][j]表示原串前i个字符、逆序串前j个字符的最长公共子序列长度。边界条件当i0或j0时空串的公共子序列长度为0即dp[0][j] dp[i][0] 0。状态转移若当前位置两字符相等该字符可加入公共子序列dp[i][j] dp[i-1][j-1] 1。若字符不相等取「舍弃原串第i个字符」或「舍弃逆序串第j个字符」中的更优解即dp[i][j] max(dp[i-1][j], dp[i][j-1])。算法总时间复杂度为O ( n 2 ) O(n^2)O(n2)完全适配n ≤ 1000 n \le 1000n≤1000的数据规模。总结核心逻辑将回文最少插入问题转化为原串与逆序串的LCS问题通过二维DP计算最长公共子序列总长度减去LCS长度即为答案。关键操作逆序串构造、LCS动态规划转移、结果等价换算。效率保障千级长度的平方级运算量运行开销极低轻松通过时间限制。代码简要说明字符串构造读入原串s1下标从1开始同步构造逆序串s2即s2[i] s1[n-i1]。DP递推双重循环遍历两个字符串的每个位置按字符是否相等执行对应状态转移填充dp数组。结果计算dp[n][n]为两串的最长公共子序列长度用总长度减去该值得到最少插入字符数并输出。下标设计字符串从1开始索引天然适配DP数组的边界条件全局数组默认初始化0即可满足边界要求。输入输出使用scanf/printf保证读写效率同时天然支持区分大小写的字符比较符合题目约束。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll dp[5005][5005];chars1[5005],s2[5005];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%s,s11);nstrlen(s11);for(ll i1;in;i)s2[i]s1[n-i1];for(ll i1;in;i)for(ll j1;jn;j)if(s1[i]s2[j])dp[i][j]dp[i-1][j-1]1;elsedp[i][j]max(dp[i-1][j],dp[i][j-1]);printf(%lld\n,n-dp[n][n]);return0;}