🚧 博客系统即将搬迁，将集成到 skywt.cn/blog。欢迎体验！
📧 现在可以使用邮箱订阅本博客。欢迎订阅！

CodeForces 1215E Marbles 题解

Description

给出一个长度为 n 的数列，$2\leq n\leq 4\ast 10^5$，每个数字 $a_i$ 都在 $[1,20]$ 内。
可以对这个数列中相邻的两个数字交换位置，最终要使得相同的数字都在一起。
求最小交换次数。

LightOJ 1073 DNA Sequence 题解：字符串+状压 DP+字符串压位/搜索

Description

You are given a list of strings over the alphabet A (for adenine), C (cytosine), G (guanine), and T (thymine), and your task is to find the shortest string (which is typically not listed) that contains all given strings as substrings. If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.
Time Limit: 4 second(s)
Memory Limit: 32 MB

More...

矩阵乘法在动态规划中的应用

$$ \begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix} $$

每增加一个维度，世界便会增加无限的美感。

More...

数位 DP 入门：HDU 3555 Bomb

简单来说，数位 DP 大概就是把一个数字拆开按位进行 DP 的一种思想。

HDU 3555 Bomb

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

More...

HDU 6447 YJJ's Salesman 题解：排序+离散+树状数组

Problem Description

YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
One day, he is going to travel from city $A$ to southeastern city $B$. Let us assume that A is $(0,0)$ on the rectangle map and $B (10^9,10^9)$. YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at $(x,y)$ now $(0\leqslant x\leqslant 10^9,0\leqslant y\leqslant 10^9)$, he will only forward to $(x+1,y)$, $(x,y+1)$ or $(x+1,y+1)$.

More...

斜率优化小结

在一维线性动态规划里，我们经常见到形如 $f(i)=min/max(f(j)+c_i)$（其实可以看成 $f(i)=min/max(a_i+b_j)$ ）这样形式的转移方程。朴素做法是 $\Theta (N^2)$。显然这样的形式可以用单调队列维护，优化到 $\Theta (N)$。但是如果遇到 $f(i)=min/max(a_i\ast b_j+c_i+d_j)$ 这样的，似乎用单调队列就难以维护了……因为 $a_i\ast b_j$ 既与 $i$ 有关，又与 $j$ 有关。这时候就要用到另一种优化方式：斜率优化。

More...