算法学习笔记之 $DP$
注: 该分享适合参加 $CSP-S$ 的大佬们参考,涉及许多杂题。本分享受限于篇幅,将不会使用闫氏 $DP$ 分析法。
算法关键点:
$1.$ 发现这是一个 $DP$ 题.
$2.$ 合理设计状态
$3.$ 推出状态转移方程。
练习 $1.$ $Luogu~P2051.$ $[AHOI2009]$ 中国象棋
在一个 $n$ 行 $m$ 列的棋盘上放若干个炮 (可以是 $0$ 个),使得没有一个炮可以攻击到另一个炮,有多少种放置方法?其中 $1\le n,m\le 100$。
题解:注意到每行、每列最多只有两个炮。
考虑以行为状态递推,有注意到设计状态时并不关心具体是哪几列有炮,只关心数量。
记 $f_{i,j,k}$ 表示考虑到 $i$ 行,目前有 $j$ 列没有炮,有 $k$ 列有一个炮。(有 $2$ 个炮的列数就是 $m-j-k$)
状态转移方程易得,详见 这篇题解.
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 110, mod = 9999973;
int n, m;
int f[N][N][N];
int C(int x)
{
return (LL)x * (x - 1) / 2 % mod;
}
int main()
{
cin >> n >> m;
f[0][0][0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; j + k <= m && j + k <= 2 * i; k ++ )
{
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k]) % mod;
if (j >= 1) f[i][j][k] = (f[i][j][k] + (LL)f[i - 1][j - 1][k] * (m - (j - 1) - k)) % mod;
if (k >= 1) f[i][j][k] = (f[i][j][k] + (LL)f[i - 1][j + 1][k - 1] * (j + 1)) % mod;
if (j >= 2) f[i][j][k] = (f[i][j][k] + (LL)f[i - 1][j - 2][k] * C(m - (j - 2) - k)) % mod;
if (k >= 1) f[i][j][k] = (f[i][j][k] + (LL)f[i - 1][j][k - 1] * j * (m - j - (k - 1))) % mod;
if (k >= 2) f[i][j][k] = (f[i][j][k] + (LL)f[i - 1][j + 2][k - 2] * C(j + 2)) % mod;
}
int res = 0;
for (int i = 0; i <= m; i ++ )
for (int j = 0; i + j <= m && i + j <= 2 * n; j ++ )
res = (LL)(res + f[n][i][j]) % mod;
cout << res << endl;
return 0;
}
练习 $2.$ $Luogu~P3957$ $[NOIP 2017$ 普及组 $]$ 跳房子
跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下:
在地面上确定一个起点,然后在起点右侧画 $n$ 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:
玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。
现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能为固定的 $d$。小 R 希望改进他的机器人,如果他花 $g$ 个金币改进他的机器人,那么他的机器人灵活性就能增加 $g$,但是需要注意的是,每 次弹跳的距离至少为 $1$。具体而言,当 $g<d$ 时,他的机器人每次可以选择向右弹跳的距离为 $d-g,d-g+1,d-g+2,\ldots,d+g-1,d+g$;否则当 $g \geq d$ 时,他的机器人每次可以选择向右弹跳的距离为 $1,2,3,\ldots,d+g-1,d+g$。
现在小 R 希望获得至少 $k$ 分,请问他至少要花多少金币来改造他的机器人。
数据满足$1 \le n \le 5\times10^5$,$1 \le d \le2\times10^3$,$1 \le x_i, k \le 10^9$,$|s_i| < 10^5$。
题解:
显然可以二分答案,从而把问题转化为 能否在灵活性为 $mid$ 时得到 $k$ 分。
考虑 $DP$,设 $f_i$ 表示条到第 $i$ 个格子时可以获得的最大分数。(若无法到达第 $i$ 个格子则 $ f_i=inf $)容易写出转移方程:
记 $L=max(d-mid,1),R=d+mid$,则 $f_i=max_{L\le (x_i-x_j)\le R}f_j+s_i$.
可以用单调队列 $DP$ 优化,复杂度为 $O(nlog10^9)$。
练习 $3$: $Acwing 1069$ (由于题目来源于 $Acwing$,此处不再显示题目。)
题解:
设 $f_{i,j}$ 表示从 $i$ 到 $j$ 的所有点构成的凸多边形划分为若干个三角形后,这些三角形权值的乘积和的最小值。
转移时枚举一个分界点 $k$ 即可。注意要使用高精度才能过题 (或者 $int128$)。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef vector <int> Bigint;
void print(Bigint a) {
for (int i = a.size() - 1; i >= 0; i -- )
cout << a[i];
cout << endl;
}
Bigint add(Bigint a, Bigint b) {
if (a.size() < b.size()) return add(b, a);
Bigint c;
int t = 0;
for (int i = 0; i < a.size(); i ++ ) {
t += a[i];
if (i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
if (t > 0) c.push_back(t);
return c;
}
Bigint mul(Bigint a, int b) {
Bigint c;
int t = 0;
for (int i = 0; i < a.size() || t; i ++ ) {
if (i < a.size()) t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
bool cmp(Bigint a, Bigint b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = a.size() - 1; i >= 0; i -- )
if (a[i] != b[i]) return a[i] < b[i];
return true;
}
Bigint min(Bigint a, Bigint b) {
if (cmp(a, b)) return a;
return b;
}
Bigint multi(int a, int b, int c) { //三个整数相乘得到的结果
Bigint res;
res.push_back(1);
res = mul(res, a);
res = mul(res, b);
res = mul(res, c);
return res;
}
Bigint pluss(Bigint a, Bigint b, Bigint c) { //三个大整数相加得到的结果
Bigint res;
res.push_back(0);
res = add(res, a);
res = add(res, b);
res = add(res, c);
return res;
}
Bigint INF() {
Bigint res;
res.resize(1000);
res[res.size() - 1] = 1;
return res;
}
Bigint Zero() {
Bigint res;
res.push_back(0);
return res;
}
Bigint f[55][55];
int a[55], n;
signed main() {
cin >> n;
for (int i = 1; i <= n; i ++ )
cin >> a[i];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
f[i][j] = INF();
for (int i = 1, j = 1; j <= n; i ++ , j ++ )
f[i][j] = Zero();
for (int i = 1, j = 2; j <= n; i ++ , j ++ )
f[i][j] = Zero();
for (int len = 3; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n; l ++ ) {
int r = l + len - 1;
for (int k = l + 1; k <= r - 1; k ++ )
f[l][r] = min(f[l][r], pluss(f[l][k], f[k][r], multi(a[l], a[k], a[r])));
}
print(f[1][n]);
return 0;
}
练习 $4$: $P3628 [APIO2010]$ 特别行动队
题解:
记 $f(x)=ax^2+bx+c,s_i=\sum_{j=1}^ix_j$
设 $dp_i$ 表示前 $i$ 个士兵能形成的所有特别行动队的战斗力总和。
枚举以 $i$ 结尾的段的上一段结尾位置 $j$ ,容易写出状态转移方程:
$dp_i=max_{j=0}^{i-1}dp_j+f(s_i-s_j)$
这是一个斜率优化 $DP$ 的形式,考虑继续化简:
$~~~~dp_j+f(s_i-s_j)$
$=dp_j+a(s_i-s_j)^2+b(s_i-s_j)+c$
$=dp_j-2as_j\cdot s_i+as_j^2-bs_j+(as_i^2+bs_i+c)$
考虑 $j<k$ 时 $j$ 的转移优于 $k$,则
$dp_j-2as_j\cdot s_i+as_j^2-bs_j\ge dp_k-2as_k\cdot s_i+as_k^2-bs_k$
$2a(s_k-s_j)s_i\ge (dp_k+as_k^2-bs_k)-(dp_j+as_j^2-bs_j)$
使用斜率优化 $DP$,时间复杂度 $O(n)$。
练习 $5$: $CF1882D.$ $Tree$ $XOR$
题解:
考虑以 $1$ 为根的时候:
注意到在最终状态下,对于所有非根节点 $x$, $a_x~xor~a_{fa_x} = 0$,且 $a_x$ $xor$ $a_{fa_x}$ 只会对 $x$ 操作时才可能改变。
所以答案为 $\sum x\ne root(a_x~xor~a_{fa_x})\cdot size_x$
用换根 $DP$ 即可。
时间复杂度为 $O(\sum n)$
练习 $6$ $Luogu 1081.$ $[NOIP2012$ 提高组$]$ 开车旅行
小 $\text{A}$ 和小 $\text{B}$ 决定利用假期外出旅行,他们将想去的城市从 $1 $ 到 $n$ 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 $i$ 的海拔高度为$h_i$,城市 $i$ 和城市 $j$ 之间的距离 $d_{i,j}$ 恰好是这两个城市海拔高度之差的绝对值,即 $d_{i,j}=|h_i-h_j|$。
旅行过程中,小 $\text{A}$ 和小 $\text{B}$ 轮流开车,第一天小 $\text{A}$ 开车,之后每天轮换一次。他们计划选择一个城市 $s$ 作为起点,一直向东行驶,并且最多行驶 $x$ 公里就结束旅行。
小 $\text{A}$ 和小 $\text{B}$ 的驾驶风格不同,小 $\text{B}$ 总是沿着前进方向选择一个最近的城市作为目的地,而小 $\text{A}$ 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 $x$ 公里,他们就会结束旅行。
在启程之前,小 $\text{A}$ 想知道两个问题:
1、 对于一个给定的 $x=x_0$,从哪一个城市出发,小 $\text{A}$ 开车行驶的路程总数与小 $\text{B}$ 行驶的路程总数的比值最小(如果小 $\text{B}$ 的行驶路程为 $0$,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 $\text{A}$ 开车行驶的路程总数与小 $\text{B}$ 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
2、对任意给定的 $x=x_i$ 和出发城市 $s_i$,小 $\text{A}$ 开车行驶的路程总数以及小 $\text B$ 行驶的路程总数。
$1\le n,m \le 10^5$,$-10^9 \le h_i≤10^9$,$1 \le s_i \le n$,$0 \le x_i \le 10^9$
题解:
首先用 $set$ 处理出两人在某座城市时选择下一个目的地分别是哪一座城市。
注意到两人在某座城市时,他们的下一个目的地不会因为 $x$ 而改变(最多只是停止旅行)
考虑用倍增优化 $DP$。
设 $f_{i,j,k}$ 表示从城市 $i$ 出发,行驶 $2^j$ 天,且 $k$ 先开车,最终回到达的城市。
设 $da_{i,j,k}$ 表示从城市 $i$ 出发,行驶 $2^j$ 天,且 $k$ 先开车,小 $A$ 行驶的路程。
设 $db_{i,j,k}$ 表示从城市 $i$ 出发,行驶 $2^j$ 天,且 $k$ 先开车,小 $B$ 行驶的路程。
考虑实现一个函数 $calc(s, x_0)$,表示从 $s$ 出发, $x=x_0$ 时,两人的行驶路程,则只要不断枚举行驶 $2^j$ 后是否已经超过了 $x_0$ 公里即可,时间复杂度 $O(logn)$。
对于问题 $1$,枚举 $s$,调用 $calc(s, x_0)$ 即可。
对于问题 $2$,直接调用 $calc(s_i, x_i)$ 即可。
时间复杂度 $O((n+m)log n)$.
练习 $7$:$Luogu P3232 [HNOI2013]$ 游走
给定一个 $n$ 个点 $m$ 条边的无向连通图,顶点从 $1$ 编号到 $n$,边从 $1$ 编号到 $m$。
小 Z 在该图上进行随机游走,初始时小 Z 在 $1$ 号顶点,每一步小 Z 以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这 $m$ 条边进行编号,使得小 Z 获得的总分的期望值最小。
$2\leq n \leq 500$, $1 \leq m \leq 125000$,$1 \leq u, v \leq n$,给出的图无重边和自环,且从 $1$ 出发可以到达所有的节点。
题解:
由于边数可能到达 $O(n^2)$,考虑先统计 点的期望次数。
设 $d_i$ 为 $i$ 的度数,$f_i$ 为经过 $i$ 的期望此书。则有
$if$ $i=1$ $then$ $f_i=(\sum_{(i,j)\in E}\frac{f_j}{d_j})+1$
$if$ $1<i<n$ $then$ $f_i=(\sum_{(i,j)\in E}\frac{f_j}{d_j})$
注:由于到达 $n$ 点时便停止,所以不能考虑 $n$ 的贡献.
接下来高斯消元求解 $f_1,f_2,\cdots,f_{n-1}$。
设第 $i$ 条边的期望经过次数为 $g_i$,$E_i=(u,v)$,则有 $g_i=\frac{f_u}{d_u}[u\ne n]+\frac{f_v}{d_v}[u\ne n]$。
排序贪心,期望越大的边编号越小。时间复杂度为 $O(n^3+mlogm)$。
练习 $8$: $Luogu P3188$ $[HNOI2007]$ 梦幻岛宝珠
$01$背包问题,其中 $1\le n\le 100,1\le W,w_i,v_i\le 2^{30}$
保证每个 $w_i$ 都可以写成 $a\cdot 2^b$ 的形式, $a\le 10,b\le 30$,且答案不超过 $2^{30}$。
题解:
注意到每一个 $w_i$ 都可以被写成 $a\cdot 2^b$ 的形式,考虑按照 $b$ 分组背包。
设 $f_{i,j}$ 表示处理到第 $i$ 位,在模 $2^i$ 意义下剩余空间为 $j$ 时能获得的最大价值。
容易写出层内转移 $f_{i,j}=max(f_{i,j},f_{i,j+w_k}+v_k)$
考虑层内转移,有 $f_{i,j}=max(f_{i,j},f_{i+1,min(j\cdot 2+(w>>i\&1),10\cdot n)})$
由于 $a\le 10$,当前位所占空间最大为 $10\cdot n$,所以可以节省时间复杂度和空间复杂度。
总时间复杂度为 $O(n^2ab)$.
练习 $9$ $Luogu$ $P2150$ $[NOI2015] 寿司晚宴$
题解:
可以发现一个显然的充要条件:甲选的数字的质因数集合和乙选的质因数集合没有交集。
首先考虑如何通过 $Subtask$。
$30$ 以内只有 $10$ 个质数,考vl状态压缩 $DP$。
设 $f_{i,s_1,s_2}$ 表示当前状态考虑到数字 $i$,且甲选的数字的质因数集合为 $s_1$,乙选的数字的质因数集合为 $s_2$ 的方案数,转移时考虑数字 $i$ 给甲、给乙还是不选即可。
时间复杂度为 $O(n\cdot 2^{20})$
接下来考虑如何拿到满分。注意到一个不超过 $n$ 的数最多指挥有一个超过 $\sqrt(n)$ 的质因数。
对于每一个数,找到他超过 $\sqrt(n)$ 的那个质因数,(没有则记作 $0$),存入 $MaxPrime_i$。
从大到小考虑每一个 $j$,把 $MaxPrime = j$ 的数放在一起考虑。
$j\ne 0$ 的时候,这些集合中的数不可能同时被甲、乙两人选择。
设 $g_{s_1,s_2}$ 表示甲选的数字的质因数集合为 $s_1$,乙选的数字的质因数集合为 $s_2$,且这些数只可能给甲时方案数。
设 $h_{s_1,s_2}$ 表示甲选的数字的质因数集合为 $s_1$,乙选的数字的质因数集合为 $s_2$,且这些数只可能给乙时方案数。
初始时把 $f$ 赋值给 $g$ 和 $h$,可以在层内作类似 $Subtask$ 的转移。
$DP$ 结束后,执行 $f_{s_1,s_2}=g_{s_1,s_2}+h_{s_1,s_2}-f_{s_1,s_2}$ 即可。(由于不选择的方案会在 $g,h$ 中都被统计。
时间复杂度为 $O(n\cdot 2^{16})$。