【专题训练】《算法进阶指南》（DP基础-例题） - 解题记录

A - Mr. Young’s Picture Permutations

容易想到从高到低填，考虑如何维护横向和纵向的递减，发现横向可以以 DP 状态形式维护，纵向递减就以转移条件形式来维护。

B - LCIS

因为要求是公共子序列的原因，我们一定只会在的位置考虑转移，所以 DP 状态中有一个可以不用要求“必选”（两个字符串的子序列必须相同的缘故，对于状态，如果用了，从串最后选了，对应从串最后选了，是多少不重要，反正）

代码解释：

nmf(i, 1, n)
{
    int val = 0; // 记录 f[i-1][1~j-1] 中最优且合法的可转移值
    nmf(j, 1, n)
    {
        if (a[i] != b[j]) // 不相等，则 a[i] 无用
            dp[i][j] = dp[i - 1][j];
        else
            dp[i][j] = val + 1;// 相等，则用 val 转移
        if (b[j] < a[i]) // 当前枚举 a[i]，若 b[j] < a[i]，因为要求了 f[i][j] 中 b[j] 必选，所以 f[i][j] 就可以用来转移，更新 val
            val = max(val, dp[i - 1][j]);
        ans = max(ans, dp[i][j]);
    }
}

C - Making the Grade G

先看代码：

LL f()
{
    LL ret = 0;
    priority_queue<int> pq;
    pq.push(a[1]);
    nmf(i, 2, n)
    {
        if (a[i] < pq.top())
        {
            ret += pq.top() - a[i];
            pq.pop();
            pq.push(a[i]);
        }
        pq.push(a[i]);
    }
    return ret;
}

感觉很神秘，但是注意到，若 if 条件触发，说明当前 a[i] 不合法（假设原来 1~i-1 是合法的），花费 pq.top() - a[i]，可以将 pq.top() 和 a[i] 变为相等的一对，值域在 a[i] 到 pq.top() 之间，而我们要把这个值变成多少呢？显然是越小越好，但太小了会影响后续的合法性，所以考虑变成次大值，即 pq 中的次大值。这样就保证了当前的合法性，同时也尽可能小，贪心地最小化答案。但是注意到我们并没有显式地把 pq.top() 变成次大值，而是直接把 a[i] 放进去了，为什么呢？因为我们只关心最终的合法性，如果后面又来了个比次大值还小的数，那么我们就应当提前把 pq.top() 和 a[i] 这一对变为更小的值，然后再用一些花费把次大值和现在来的更小的数变为相等的一对，这样就更省钱了。实际上它们的值是不定的，但肯定是在 a[i] 到 pq.top() 之间的某个值（如果没有被再次操作的话），所以我们直接把 a[i] 放进去，这样在后面可能产生的花费肯定最小，这样做其实保证了合法性，同时也保证了答案的最优。

D - Mobile Service

将 DP 状态从 dp[i][j][k][l] 优化到 dp[i][j][k] 是好想的，因为 l 显然在 p[i-1] 这个位置上，如果不需要记录方案的话，就已经做完了，转移方程大概是下面这个样子，当然实际还要判断各个员工的位置不重合。

1
2
3

f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + c[p[i - 1]][p[i]]);
f[i][p[i - 1]][k] = min(f[i][j][k], f[i - 1][j][k] + c[j][p[i]]);
f[i][j][p[i - 1]] = min(f[i][j][k], f[i - 1][j][k] + c[k][p[i]]);

但是需要记录方案，该怎么做呢？我们可以记录来到 p[i] 的人原来的位置，因为保证了三人不会重合，所以记录下来就能唯一确定是谁来了 p[i]。所以我们可以定义一个三维数组 pre[i][j][k]，表示来到 p[i] 的人原来的位置是 pre[i][j][k]，这样就能唯一确定是谁来了 p[i]，从而在最后倒推方案。

代码中倒退方案得到的 u[i] 不是指第 i 个人来到 p[i]，而是指来到 p[i] 的人原来的位置是 j，k还是 p[i-1]，最开始顺序是 1(j),2(k),3(p[0])，然后根据 u[i] 不断交换，最后就能得到每个人的当前位置以输出（代码中 o[0/1/2] 表示在 j/k/p[i-1] 的人的编号）。

E - 传纸条

直接暴力 DP，状态 f[i][j][k][l] 表示上面一条传递路径到达 (i,j)，下面一条传递路径到达 (k,l) 时的最小代价。因为要保证两条路径不相交，所以每次只枚举。

转移方程如下：

f[i][j][k][l] = max(f[i][j][k][l], max(max(f[i - 1][j][k - 1][l], f[i][j - 1][k - 1][l]), max(f[i - 1][j][k][l - 1], f[i][j - 1][k][l - 1])) + a[i][j] + a[k][l])

初始状态 f[1][1][1][1]=0，目标状态 f[n-1][m][n][m-1]（因为两条路径不能相交，最后一步只能到达 (n-1,m) 和 (n,m-1)）。

F - I-Country

从任何一个正方形到另一个正方形只能沿着两个方向移动（从下列列表中选择：左、右、上、下；对于不同的正方形对，方向可能不同）

这玩意什么意思？其实是 A 国占领区域是一个凸包 ~~，但我也不知道为什么。~~

设状态 f[i][l][r][j][0/1][0/1] 表示当前在第 i 行，左边界是 l，右边界是 r，已经占领了 j 格，左边界方向是 0/1（表示左/右），右边界方向是 0/1（表示右/左）时的最大收益。

转移还是好想的，枚举 i l r j d1 d2，然后枚举上一行的左边界 p 和右边界 q，注意到 p 和 q 的范围是受 d1 和 d2 限制的。

如下：

方案输出时，记录 pa[i][l][r][j][d1][d2] 表示从上一行的哪个 p 和 q 转移过来，然后倒推输出。

实际代码对状态做了一些压缩优化，把 [d1][d2] 合并成了 [0/1/2/3]。

G - Cookies

前面的贪心是好想的，显然应把更多的饼干分给贪婪度大的孩子，于是需要按贪婪度从大到小考虑孩子，设计 DP 状态有两种思路：

表示第个孩子拿个饼干时的最优答案，然后发现这玩意根本无法转移，因为你不知道总共用了多少饼干。
表示前个孩子拿个饼干时的最优答案，发现很难转移啊，因为要枚举第个孩子的饼干数，转移至少显然无法接受。

但我们也只有第二种 DP 状态可能了，考虑挖掘性质优化转移。

然后就有一个很妙的性质：若给第个孩子大于 1 个饼干，有，挺显然的，就是对所有孩子少给一个，相对大小关系不变，答案不变。

有了这个性质，我们就只需要枚举给第个孩子 1 个饼干时的答案，这该怎么做呢？发现单纯想知道第个孩子的贡献需要枚举它前面有多少个与他获得饼干数相同的孩子，发现是一个的枚举，可以接受，实现上没必要记录一些很神的东西来辅助转移，因为假若是从到都给 1 个饼干，那么这一段孩子都有个比他多的，产生的贡献，直接从加上这坨贡献就是转移方程。

H - 小 A 点菜

唐题。

I - 正整数拆分

唐题。

J - Jury Compromise

作为花费，作为价值，普通的 01 背包，表示前个人，的最大价值，注意到和可能为负，前者对应加上一个偏移量，后者对应滚动数组优化后花费为负正着循环，反之倒着循环，为零时随意。

方案输出是普通的，一个三维数组记录来时路（？）即可。

K - Coins

至今不会的单调队列优化多重背包 DP，也不会神秘贪心优化。

因为 bitset 优化是的，跑得还比上面的快。

L - 石子合并（弱化版）

唐题。

M - Polygon

唐题。

N - 金字塔

有趣的题目。

Y - Connected Graph

计数 DP，定义状态表示有个点的无向连通图的数量。考虑 1 号点所在的连通块，假设这个连通块有个点，则要从剩下的个点中选出个点，有种方案，这个点组成一个连通块有种方案，剩下的个点可以随意连，有种方案，这样一定是一个非连通图，用全方案减去非连通图就能得到连通图数量。

所以有状态转移方程：

Z - How Many of Them

首先设计状态表示有个点，条割边的无向连通图的数量。先计算，发现此时就是一个边双联通分量，显然有，其中表示个点的所有无向连通图数量，的计算见 Y - Connected Graph。

然后计算，依然考虑 1 号点所在的边双联通分量，这样才能不重复计数。假设 1 号点所在的边双联通分量有个点，则要从剩下个点中选出个点，有种方案。这个点组成一个边双联通分量有种方案，剩下的个点和这个点之间要有条割边连接，也说明剩下的个点要分成个连通块，每个连通块通过一条割边和这个点之一（1 号点所在边双内的点）连接，有种连法（注意到此时我们把这个连通块当做缩点后的点来考虑，因为我们不知道各个连通块有多少个点）。

注意到，除去这条割边后，剩下的图中，这个点和这个点之间没有边连接，是单独的子问题，所以我们可以定义一个新的状态，含义如下：

设有个点分成个连通块，每个连通块选出一个点伸出一条边（来连接 1 号点所在的边双），累计伸出条边以连接 1 号点所在边双，有条割边的无向图数量为。

则有状态转移方程：

然后考虑如何计算，注意到现在我们是在单独考虑一个新的子问题，考虑一个“新的”1 号点所在的连通块（或者是去掉 1 号点所在的边双联通分量后编号最小的点），假设这个连通块有个点，则有种选法，这个点组成一个连通块，这个连通块有条割边，方案数为，还要选一个点伸出一条边，有种方案，剩下的个点要分成个连通块，有条割边连接，方案数为。

所以有状态转移方程：