2020.10.29部分分题解

CNF_Acceptance · 2020-10-30 11:22:36 · 个人记录

T1 第一饭堂（CF118C）

题意简述：给出一个 n 位数，改变其中的一些数位使得有 k 个数相等，改变一个数需花费两个数的差的绝对值，求最少的花费并输出字典序最小的方案。

• $dfs$ 枚举全排列，选出花费最小的方案，全排列从1开始搜，保证字典序最小，加上最优性剪枝，期望得分： $30pts

  时间复杂度： O(n!)

• 70pts$ $DP

  考虑 DP ，枚举最终答案中有 k 个相同的数 x \ (0 \le x \le 9 且 x 为整数 )

  设 f_{i,j} 表示数列前 i 个数中有 j 个数等于 x 的最小花费，则：

  \displaystyle f_{i,j} = \min(f_{i-1,j},f_{i-1,j-1}+ \mid a_i-x \mid) f_{i,j}$ 的值为：前 $i-1$ 个数选了 $j$ 个 $($ 即第 $i$ 个不变 $)$ 与前 $i-1$ 个选 $j-1$ 个加上第 $i$ 个改变的花费。期望得分： $70pts

T2 第二饭堂（CF7D）

• 部分分 ： 递归

  由题意可知： 若 A 为回文串，则其 "回文度数" 为 A 长度为 \lfloor \frac{n}{2} \rfloor 的子串的 "回文度数" +1。

  若串 A 不为回文串，则其 "回文度数" 为 0

  因此进行递归:

T3 第三饭堂（CF29E）

咕~(还没改粗来QWQ)

直接输出-1