Ruins He's house

这道题应该是背包问题里堪称经典的问题了，表示刚开始学 DP，这类问题也很快弄懂了。

这类问题要用到两个数组，$dp[0][i]$ 表示 $i$ 块钱可以买到的最大价值，$dp[1][i]$ 表示考虑到当前盒子时，$i$ 块钱可以买到的最大价值，首先 $dp[0]$ 置为 $0$，枚举全部的盒子，$dp[1]$ 置为$-\infty$ 表示买不到，更新的转移可以从 $dp[0]$ 转移也可以从 $dp[1]$ 转移，从 $dp[0]$ 转移表示你还没有买盒子，要附加上盒子的价格，$dp[1]$ 表示你买过盒子了，就直接转移就可以了，转移方程如下:

$$dp[1][k] = \max \begin{cases} dp[1][k] \\ dp[1][k-c[i][j]]+v[i][j] \\ dp[0][k-c[i][j]-p[i]]+v[i][j] \end{cases}$$

注意每次 $dp[1]$ 的置 $-\infty$ 操作，以及每次枚举完当前盒子后用 $dp[1]$ 更新 $dp[0]$ 的值。

$$dp[0][j]=\max(dp[0][j],dp[1][j])$$

嗯，今晚状态不错，除了卡最后一题以外没有什么太大的问题。

最后一题到最后还是 wa 了，估计卡精度卡的不够好。

好吧，今天开始正式学 DP，随便点了一个简单题，练了下手。。。

这道题转移方程不难，$O(n^2)$ 的复杂度，可以 AC。

$dp[i][j]$ 表示考虑跑了 $i$ 趟前 $j$ 个车走完花的时间

先进行对时间排序 (不知道为什么，第一次交没排序也 AC 了。。。。难道是原来就是有序的？)

$i \leq n$ 时：$dp[1][i] = a[i]+t$
$i>n$ 时：$dp[1][i] = \infty$

至于趟数大于 $1$ 的，有如下转移方程：

$$dp[k][i] = \min\{\max(dp[i-1][j][j-1]+t, a[i])+t\}$$

其中

$$\max(i-n+1,1) \leq j<i$$

然后找 $dp[i][m]$ 中最小的就可以了

好吧，我承认这个数独的图不好弄，建图建了好久，才想到每一行就四个结点，数独转化为精确覆盖问题的方法还是参照 Knuth 的论文，如果读取到一个格子是空的，那么加 $9$ 行，分别表示这个格子填 $1$ 到 $9$ 这 $9$ 个数字，如果读取到的格子是一个数字，那么就加一行就可以了，然后列有 $9 \times 9 \times 4$ 列，前 81 列表示这一行表示填的是第 $i$ 行第 $j$ 列的格子，接下来 $81$ 列表示第 i 行填写 $k$，接下来 $81$ 列表示第 $j$ 列填写 4，最后 $81$ 列表示对应九宫格填写 $k$。转化为精确覆盖之后，直接跑 dlx 的 dfs 就可以了，主要还是建图，对于 3076 的 $16 \times 16$ 做法如出一辙。

这题因为建图卡了好久，Dancing Links 的入门题，不想多说什么。想了解的请参看 Knuth 的论文。

这里学会了一个很方便的双向链表插入算法，如果要将 $x$ 插入到双向链表中，只要先更新 $x$ 的指针域，然后调用 dlx 的第二步就可以了。

在 init 函数有所实现。