P10967设在\(1\simi\)装了\(j\)个邮局的答案\(f_{i,j}\)：\(f_{i,j}=\min\{f_{k,j-1}+w_{k+1,i}\}\)，其中\(w_{l,r}\)为\(l\simr\)有一个邮局的最小距离。\(w_{l,r}\)怎么求？在中位点装邮局。那么有\(w_{l,r}=w_{l,r-1}+x_j-x_{[(i+j)/2]}\)。其中\(x\)是村庄位置。

原题链接题解1.把字符串倒过来，记作\(S_1\)其最大公共子串是回文串，所以这部分可以不用求，字符串长度减去最大公共子串的长度就是答案2.怎么求最大公共子串的长度呢？假设我们已经知道字符串a和字符串b及其所有子串的lbs，此时往字符串b末尾添加一个字符c变成字符串b1，而字符串a中以

原题链接：https://www.luogu.com.cn/problem/P1435解题思路：方法1：回文字串的特点是，正着读、反着读是一样的换一个思路，对于一个字符串s，正序、逆序公共的部分就是已经是回文的部分，剩余的部分就是要插入的字符所以，问题转换为，计算一个字符串正序、逆序的最长公共子串，然后剩下的长度

题目：链接：https://www.luogu.com.cn/problem/P1435观察到：在里面插入字符不会影响外面的配对所以以dp[i][j]记录字符串s下标从i到j变化到回文串步数，那么递推公式：if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];elsedp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;就是说如果最外面能