Second Day
Zero_Sky
·
·
个人记录
\huge\color{blue}\text{DP}$ $\tiny\color{pink} dynamic programming $ $\huge\color{blue}\text{动态规划}
例题
\color{lightblue}\large T3
- 滑雪
-
- 每个格子有高度 h_i
- 可以滑向周围四个比自己矮的格子
- 最多能滑多远
可以看成二维的最长下降（或者反过来的最长上升）的走法
所以
- 状态：f_{i,j} 表示从 (i,j ) 出发能滑的最长长度
- 转移：f_{i,j} = max(f_{x,y}) + 1, (|x - i| + |y - j| = 1 且 h_{x,y} > h_{i,j})
\large \color{orange}\text{or}
一维方法
可以将 h_i 从低到高排序，即
| h_1 < |
h_2 < |
h_3 < |
\cdots |
< h_{n\times m} |
| (x_1,y_1) |
(x_2,y_2) |
(x_3,y_3) |
\cdots |
(x_{n\times m},y_{n\times m}) |
所以滑雪方向一定是从左向右滑的
- 状态：f_i 表示滑到 (x_i,y_i) 时的最长长度
- 转移：f_i = \max\limits_{ 1 ≤ j < i }(f_j + 1) ( |x_i - x_j| + |y_i - y_j| = 1) ，j 可以不枚举，找周围4个在前面的即可
\large\color{pink}\text{等同于一个拓补排序}
\small\color{pink}\text{同时，和拓补排序有关的题，一般是DP（有一类题，拓补排序完直接DP）}
\tiny\text{动态规划技巧:}$ $\color{orange}\text{改变DP顺序，达到更好的写法}
\color{lightblue}\large T4
- 乌龟棋
- 长度为 N 的格子上有权值
-
- 使用一张牌往前走几步
- 最大化经过的位置的权值和
\large\color{pink}\text{发生变化的量就是存在状态中的量}
所以 可以用 i 表示跳到哪儿了，a_1,a_2,a_3,a_4 分别表示对应牌用了几张\
即
- 状态为 f_{i,a_1,a_2,a_3,a_4} 调到 i 位置分别用 1-4 的牌 a_1,a_2,a_3,a_4 张时最大的权值
- 对应转移为4种
\text{用第一张牌 } -> a_1 + 1 \\
\text{用第二张牌 } -> a_2 + 1 \\
\text{用第三张牌 } -> a_3 + 1 \\
\text{用第四张牌 } -> a_4 + 1 \\
\end{cases}
∵a_1 + a_2 + a_3 + a_4 = \text{当前走的步数}
（五维状态间存在等式关系）
∴i = a_1 \times 1 + a_2 \times 2 + a_3 \times 3 + a_4 \times 4
所以
- 首先要\color{orange}\text{确定题目的状态}，题目中有6个变量是变化的，所以可以用其中5个作为状态，一个作为DP的值，即一个五维DP
- 其次五维DP里面\color{orange}\text{有一个值是冗余的}，所以可以优化为一个四维DP
总结DP技巧
-
\color{orange}\text{状态设计}
-
\color{orange}\text{增加维度}
-
\color{orange}\text{求方案数}
-
\color{orange}\text{改变顺序}
-
\color{orange}\text{消除冗余}
区间DP
例题
\color{lightblue}\large T1
状态： f_{l,r} 代表把第 l 堆石子到第 r 堆石子合并成一堆石子的最小代价
\small\color{pink}\text{（注意，区间DP前两维空间是左右端点）}
初始化： f_{i,i} = 0
转移： f_{l,r} = \min\limits_{(l ≤ k < r)}(f_{l,k} + f_{k + 1,r} + a_l + a_{l+1} + \cdots + a_r)
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; i++)
f[i][j] = 0;
for(int len = 2; len <= n; len++)
for(int l = 1, r = len; r <= n; l++, r++)
for(int k = j; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + sum[l ~ r]);
\text{\small注意：\color{pink}\large 枚举时先枚举区间长度，再枚举区间端点，再枚举断点}
环形一共有 n 条边，合并需要 n-1 次，所以必定有一条边用不上
所以，一定存在一个地方把环断开成一条链
\text{\small常见做法：\color{pink}\large 将序列在后面抄一遍，对新序列做区间DP}
即\begin{cases}
\text{从} a_n \text{和} a_1 \text{处断开，} a_1, a_2,\cdots,a_{n-1},a_n\text{。\ 答案是} f_{1,n}\\
\text{从} a_1 \text{和} a_2 \text{处断开，} a_2, a_3,\cdots,a_{n},a_1\text{。 \ \ \ \ 答案是} f_{2,n+1}\\
\text{从} a_2 \text{和} a_3 \text{处断开，} a_3, a_4,\cdots,a_n,a_1,a_2\text{。答案是} f_{3,n+2}\\
\cdots\\
\end{cases}
对于环，答案就是
\min\limits_{i=1,\cdots,N}(f_{i,i+N-1})
\color{lightblue}\large T2
- 给出一个只有{(\ )[\ ]}四种括号组成的字符串
- 求最多能够选出多少个括号满足完全匹配
\small\color{pink}\text{（区间DP前两维空间是左右端点）}
状态： f_{l,r} 来表示从 l 到 r 的区间内最多有多少匹配
即将原区间拆成两个区间，当左右两个区间都匹配好，那么这整个区间就匹配好了
转移： f_{l,r} = \min\limits_{(l≤k<r)}(f_{l,k} + f_{k+1,r})
但是，存在一种情况，左右无法断开
当中间有完美匹配且左端点和右端点可以匹配时
即 s_l 和 s_r 能匹配
所以另一个转移： \text{当}\ s_1=s_2\ \text{时},f_{l,r} = f_{l-1,r-1} + 2
转移：
f_{l,r} = max
\max\limits_{(l≤k<r)}(f_{l,k} + f_{k+1,r})\\
f_{l-1,r-1} + 2\ \ (s_l=s_r)\\
\end{cases}
\color{lightblue}\large T3
- 给定凸 N 边形
- 每个点有一个权值
- 将凸多边形三角化
- 每个三角形的三个点权值乘起来求和
- 问最小和
$\large\color{pink}\text{本质上是个环形DP}
状态：用 f_{l,r} 表示区间 l 到 r 间最小权值和
将序列拷贝多份
如果要求 f_{1,9} ，可以在 a_1 到 a_9 （a_{8+1}）中拉一条线,将其分成两半（互不干扰）
所以转移： f_{l,r} = f_{l,k} + f_{k,r}
初始化：当区间只包含3个值时，求一下区间的权值和
背包
-
- 最基础的背包（\ 0\ 1背包）：
- 有 N 种物品，一个体积为 M 的包
- 物品 i ：体积 V_i，价值 W_i
-
\color{orange}\text{每个物品选或不选}
- 能装下的物品价值最大值
-
- 无穷背包问题：
- 有 N 种物品，一个体积为 M 的包
- 物品 i ：体积 V_i，价值 W_i
-
\text{每种物品可以选\color{orange}任意多个}
- 能装下的物品价值最大值
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
//当前遍历的物品
f[i+1][j+v[i]]=max(f[i][j]+w[i],f[i+1][j+v[i]]); //选
f[i+1][j]=max(f[i+1][j],f[i][j]);//或不选
-
- 有限背包问题：
- 有 N 种物品，一个体积为 M 的包
- 物品 i ：体积 V_i，价值 W_i，个数 K_i
-
\text{物品}\ i\ \text{可以选\color{orange}至多}\color{orange} K_i \color{orange}\text{个}