Bajka
题面
Fabijian 有两个字符串 , $afraid$ 和 $like$ .
将 $like$ 重构得到 $s$ 使其等于 $afraid$ , 有以下 2 中操作 :
1 . ( 如果有的话 ) 向左或向右移动 1 个字符 , 将移动后的字符添加到 $s$ 的末尾 .
2 . ( 如果有的话 ) 移动到与当前字符相同的字符上 , 无添加操作 .
每次移动的代价为两个字符的距离 , 总代价为 $cost$ .
最小化 $cost$ .
解题思路
显然的 $dp$ .
设 $dp_{i,j}$ 表示当前正在 $afraid$ 的第 $i$ 个位置 , 写下一个字符 $like_j$ 所需要的最小的代价 , 转移为 :
$$dp_{i,j} = \min{dp_{k,j - 1} + c}$$
在这种情况操作 2 是极为耗费时间的 , 显然不优 , 新的转移 :
1 . $dp_{i,j}$ 尝试向 $dp_{i \pm 1,j + 1}$ 转移 , 其中 $afraid_{i \pm 1} = like_{j + 1}$ .
2 . 从 $dp_{i,j}$ 向 $dp_{k,j}$ 转移 , 其中 $afraid_j = afraid_k$ . 前缀和优化到 $O(m)$ .
复杂度 $O(nm)$ .
$\text{序列修改}$
题面
有一个序列 $a$ , 定义其频度序列 $c$ , 其中 $c_i$ 表示 $a_1$ 至 $a_i$ 中不同数的个数 .
修改 $a$ 中的元素的代价为修改前后的差的绝对值 , 记为 $cost$ .
最小化 $cost + \sum_{i = 1} ^ {n} i \times c_i$
解题思路
每个数字的只有第一次出现时会对 $c_i$ 产生贡献 , 设 $i$ , $j$ 分别为 $a_i$ , $a_j$ 分别第一次出现的位置 , $k$ 为 $a_i$ 下一次出现的位置 , $S_i$ = $\sum_{j = i}^{n} j$ .
分类讨论 :
能够产生贡献的只有 $2$ 种情况 .
1 . $i > j$ , 新增的 $cost$ 为 $\lvert a_i - a_j \rvert - S_i + S_k$ , 用 $set$ 找到 $a_i$ 前最近的 $a_j$ .
2 . $i < j \ and \ j < k$ , 新增的 $cost$ 为 $\lvert a_i - a_j \rvert + S_i - S_j$ . 再次分类讨论 :
- $a_i > a_j$ : 代价为 $(S_k + a_i)$ - $(S_j + a_j)$ .
- $a_i < a_j$ : 代价为 $(S_k - a_j)$ - $(S_j - a_j)$ .
树状数组维护 .
复杂度 $O(n \log n)$