[IOI2000] 邮局 加强版 题解 考虑动态规划，设 f i , j f_{i,j} fi,j​ 为经过了 i i i 个村庄，正在建第 j j j​ 个邮局的最优距离。 以及 w i , j w_{i,j} wi,j​ 表示区间 [ i , j ] [i,j] [i,j]​ 内建一个邮局时的距离总和。 a a a 数组表示每个村庄的坐标编号。 朴素版状态转移方程： f

快速链接 原题链接题目大意输入格式输出格式数据范围解题思路上代码 原题链接 P1435 题目类型： 普 及 + / 提 高 {\color{yellow} 普及+/提高} 普及+/提高 AC记录：Accepted 题目大意 回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。