动态规划

· · 个人记录

ACwing271 杨老师的照相排列

我们可以从高到低依次考虑标记为 1\sim n 的学生排的位置（即 \text{dp} 转移顺序）

在任意时刻，已经安排好位置的学生在每一行中占据的一定是从左端开始的连 续若干个位置，用一个 k 元组 (a_1,a_2,...,a_k ) 表示每一行已安排的学生人数，那么还有一个性质是 a_1\ge ...\ge a_k。

所以我们的状态函数可以定义为 f[a_1,a_2,a_3,a_4,a_5] 表示各排从左起分别站了 a_1,a_2,a_3,a_4,a_5 个人时，合影的方案数量。

边界：f[0,0,0,0,0]=1，其余都为0。目标：f[N_1,N_2,N_3,N_4,N_5]。转移比较简单，刷表法 好写一点

ACwing276 I-区域

我们设计出状态函数：f[i,j,l,r,x,y] 表示前 i 行选择了 j 个格子，其中第 i 行选择了 [l,r] 个格子（若不选则均为 0），左边界的单调性类型为 x，右边界单调性类型为 y（0 表示递增，1 表示递减）时，能构成的凸连通块的最大权值和。

边界：f(i,0,0,0,1,0)，目标：\max\{f[i,K,l,r,x,y]\}。

本题还需要输出方案，所以建议使用 填表法 ，用一个数组来记录每个状态的最优解从何处转移过来，从来方便输出方案

P6280 USACO20OPEN Exercise G

根据 置换 的知识，我们有一个结论。对于自然数 n 的任何拆分比如 n=a_1+\cdots+a_m，k 为 a_1,...,a_m 的最小公倍数

我们可以考虑，对于某一个 k，是否能找出自然数 n 的一个分拆，使得他们的最小公倍数等于 k。

由于可以拆出 1，也就是对于 k=[b_1,b_2,...,b_m]，我们希望 b_1+b_2+...+b_m 尽量小，需要 \le n。所以我们需要知道 k 确定的时候，b_1+b_2+...+b_m 最小是多少。还有一个很明显的结论，最小的情况是，假设 k 的质因数分解为 2^{c_1}\times 3^{c2}\times \cdots ，那么最小为 2^{c_1}+ 3^{c2}+ \cdots。

这时候就成了一个类似于多重背包的问题。我们令 f(i,j) 考虑到第 i 个质数的时候，并且总和不大于 j 的时候，所有 k 的和。可以用滚动数组优化掉第一维

P6147 USACO20FEB Delegation G

首先我们发现枚举 k 应该无法避免，并且不整除 n-1 的 k 显然可以排除

我们发现对于一棵子树而言，经过子树的根节点 的链只有两种可能：

$2.$ $v\rightarrow u\rightarrow f$，$v$ 是 $u$ 的子树内的某个点，$f$ 是 $u$ 的某个祖先节点。并且显然对于每个 $u$，第二条链最多只有一条 于是我们可以对每个点 $u$ 去维护其等待配对的子链的列表，每次遍历到 $u$ 的一个子节点 $v$ 的时候，将经过 $v$ 的子链尝试去列表中的子链配对，配对失败则加入列表。如果遍历完 $u$ 的所有子节点后，待配对的子链 $>1$，则无解 [UVA1336 修缮长城](https://www.luogu.com.cn/problem/UVA1336) 首先肯定是一个 **区间** $\text{dp}$。剩下的状态需要：2当前的位置在区间的左端点还是右端点和当前的时间 但时间这一维太大了，可以考虑 **费用提前**。令 $f(i,j,k)$ 表示修复完区间 $[i,j]$ 的所有点，且当前位置在 $k$（$k=0$ 表示在左端点，$k=1$ 表示在右端点）时，已经发生的总费用与所有“肯定会发生的未来费用”之和 [CF1579G Minimal Coverage](https://www.luogu.com.cn/problem/CF1579G) 可以发现最后的答案不超过 $2\times l_{max}$。所以开始设计 $\text{dp}$ 的状态：$f(i,l)$ 用来表示当前第 $i$ 条线段的结束点到最左边的距离是 $l$ 时，到最右边的距离最小值。于是当前覆盖的长度即为 $l+f(i,l)$。最后的答案即为 $\min(l+f(n,l))

预处理：f(i,j)=inf，f(0,0)=0

对于 a_{i+1}，如果向左放，那么到左边界的距离变为 \max(l-a_{i+1},0)，到右边界的距离为 f(i,l)+a_{i+1}（因为向左跳了那么多），所以 f(i+1,max(l-a_{i+1},0))=\min(f(i,l)+a_{i+1})

如果考虑向右放，那么到右边界的距离变为 \max(f(i,l)-a_{i+1},0)，到左边界为 l+a_{i+1}，所以 f(i+1,l+a_{i+1})=\min(\max(f(i,l)-a_{i+1},0))

CF1710C XOR Triangle

结论：a\oplus b=a+b-2\times(a\&b)，所以 a\oplus b=a\oplus c+c\oplus b-2\times ((a\oplus c)\&(c\oplus b))

所以 x+y\ge z 是肯定满足的，但是我们要做到不能取等号就要求 x,y,z 的两两按位与不能为 0。

然后我们 按数位来 \text{dp}，从高位到低位，用三个 0/1 变量表示 a,b,c 是否满足已经填的位都和 n 相同的限制，再用三个变量 x,y,z 来表示 x\&y，y\&z，x\&z 是否仍然为 0。然后枚举 a,b,c 这一位都填了什么来转移。复杂度为 O(2^9n)。

P6748 『MdOI R3』Fallen Lord

中位数 \le a_u 这个限制相当于 >a_u 的数不超过 \left \lfloor \dfrac{deg_u-1}{2} \right \rfloor 个

设 dp[u][0/1] 表示考虑以 u 为根的子树，u 的父边是否可以 >a_u 的答案

转移的时候先对于 u 的每个儿子，求出 (u,v) 这条边在 \le a_u 和 >a_u 两种情况下的最大答案，设为 w[v][0/1]。先默认所有的 (u,v) 都选 w[v][0]，然后按照 w[v][1]-w[v][0] 从大到小排序贪心选择即可（反悔贪心）

CF815C Karen and Supermarket

优惠券的依赖关系显然形成一个森林结构。所以我们考虑 树形 \text{dp}。我们发现去算购买 i 件商品最少花多少钱会更方便。

设 f(u,j,0/1) 是以 u 为根的子树中，用或不用优惠券的时候，选 j 件物品的最小代价。我们会发现这个转移也是一个 树形背包

树形背包要写复杂度为 O(n^2) 的代码是有讲究的，不然复杂度会退化

void dfs(int u){
    siz[u]=1;
    dp[u][0][0]=0; dp[u][1][0]=c[u]; dp[u][1][1]=c[u]-d[u];
    for(auto &v: g[u]){
        dfs(v);
        for(int j=siz[u];j>=0;j--){
            for(int k=0;k<=siz[v];k++){
                dp[u][j+k][0]=min(dp[u][j+k][0],dp[u][j][0]+dp[v][k][0]);
                dp[u][j+k][1]=min(dp[u][j+k][1],dp[u][j][1]+min(dp[v][k][0],dp[v][k][1]));
            }
        }
        siz[u]+=siz[v];
    }
}

CF1280D Miss Punyverse

首先把点权减一下，然后合法条件变成连通块内点权之和 >0。

设 f(u,j) 表示以 u 为根的子树选 j 个连通块最大合法连通块数量。我们发现包含根节点的连通块是可以和父亲以及父亲的其他子树的带根连通块合并的，所以我们还希望在合法连通块数量最大的同时，带根连通块的权值最大，我们另开一个 g(u,j) 记录以 u 为根的子树选 j 个连通块在合法连通块数量最大的情况下带根连通块的最大权值。

然后转移就是一个树形背包了，按照树形背包的套路进行转移即可。

P7519 省选联考2021 滚榜

其实 状压 的状态设计很容易，设 f(S,i,j,k) 表示前公布的队伍状态为 S，最后一位是 i，已选择 b_i 总和是 j，上一个 b_i 为 k 的方案总数。然后枚举下一个公布的队伍进行转移。复杂度为 O(2^nn^2m^2) 过大，需要优化

发现只用求排名的总方案数，而与 b_i 分配方式无关，考虑贪心地分配使得每个位置的 b_i 尽量小的方式满足条件，就可以将状态中的 k 一维去掉

考虑对贡献进行简单变形：\sum b_i=\sum \max(a_{i-1}-a_i,0)\times (n-i+1)，类似于费用提前计算，因为题目要求 b_i 不降，如此可以甩掉枚举上一个 b_i 的值这一步

最后统计 f(U,i,j) 的和即可。时间复杂度 O(2^nn^2m)

UVA10891 Game of Sum

设 f(i,j) 是取到区间 [i,j] 时先手能取到的最大分数，那么在区间 [i+1,j] 或区间 [i,j-1] 中此时的先手就变成了后手，所以先手的分数是区间 [i+1,j] 或区间 [i,j-1]的和减去 f(i+1,j) 或 f(i,j-1)。这里可以使用前缀和优化。

CF1527E Partition Game

先去思考 c 的求法，我们有 c(i,j)=c(i,j-1)+j-lst_{a_j} 其中 lst_{a_j} 是 a_j 最后一次出现的位置，若没有，则 c(i,j)=c(i,j-1)

再考虑转移，固定 j，考虑 i 到 i+1 的变化

f(j,i)=\min\{f(j-1.k-1)+c(k,i)\}$，$f(j,i+1)=\min\{f(j-1.k-1)+c(k,i+1)\}

发现首先是 k 多了一项，然后对于 k\le lst_{a_i+1} 的都要加上 i+1-lst_{a_i+1}，其他都不变。也就是区间加法和区间最小值，用线段树维护。时间复杂度 O(kn\log n)

P5664 CSP-S2019 Emiya 家今天的饭

可以看出，维护每列已选的节点复杂度太大，不太可行；因此正难则反，先不考虑每列不超过一半的这个限制，求出总方案数 ans1=\prod_{i=1}^{n} (sum[i]+1)，然后再减去考虑这个限制后不合法的方案数。现在问题就变成，求任意列选的节点超过所有选的节点的一半的方案数之和

显然，在一个方案中，只可能有一列的节点超过所有选的节点的一半。因此可以想到枚举这个超过限制的列，然后对于这个列进行 \text{dp}

设现在枚举到第 k 列，dp[i][s1][s2] 表示前 i 行，多余的列选了 s1 个，其余列选了 s2 个的方案数，但这样时间复杂度是 O(n^3m) 的

考虑优化，由于我们并不关心这两种具体选了多少个，我们可以将状态改为 dp[i][j] 表示前 i 行，多 - 少 =j 的方案数，转移很简单，最后统计 j\ge 0 的方案总数就可以了

注意负下标的处理和前后两行下标的对应关系

CF1785D Wooden Spoon

这个题目拿到需要有第一直觉是 \text{dp} 题。为何有这个第一直觉的，比如一个数字为 i 的人。那么首先他第一轮要输给一个比它大的数字 j。那么假设 j 在第一轮比赛后，剩下来的数字是第 j_2 小的数，那么这就是一个子问题了

可以考虑一下终态，钦定的一条链，有 x_1<x_2<\cdots<x_n<2^n，那么 x_i 的另一边子树中怎么安排其实是很随意的

手推一下，容易写出在链固定时，x_i 子树内方案数为 C_{x_i-2^{i-2}-1}^{2^{i-2}-1}\times 2\times (2^{i-2}!)

发现式子是一堆东西 乘起来 的样子，于是就可以 \text{dp} 了，接下来从后往前 \text{dp}，令 f(i,j) 表示 x_i=j 的时候前面的式子从这一项开始的式子的积

则 f(i,j)=C_{j-2^{i-2}-1}^{2^{i-2}-1}\times 2\times (2^{i-2}!)\times \sum\limits_{k=j+1}^n dp[i+1][k]

中间求个后缀和，就解决了