【学习笔记】dp 状态与转移

Ehab and the Expected GCD Problem

思维还是慢了一步 。

observations + dp 。

这题难在 dp 阶段的设计 。 我们考虑从前往后向序列中填数 ，同时记录当前前缀 gcd 状态。

dp[i][j][k] 表示考虑了前 i 个数，前缀 $\gcd =2^{\text{j}}{3}^{\text{k}}(k=0/1)$ 。转移是巧妙的 。（乘法原理）

Three Servers

看完题意我是 joker …

简单的背包问题可以让你怀疑人生 …

可达性 dp -> 最优性 dp

observations + dp

同为可达性 dp ：https://blog.csdn.net/cqbzlydd/article/details/124870640?spm=1001.2014.3001.5501

Hero meet devil

毋宁是状压好题 。

observations + dp

Min Product Sum

dp（x）
数学（v）

干瞪眼大法 …

我怎么看不懂题解啊

Salvage Robots

大受震撼 …

强行构造状态和dp阶段 …

膜拜 idsy …

考虑中间有一个安全区域 … 四周为危险区域 …

考虑将安全区域拖动，这样危险区域中的一些 robot 会被甩出去 …

设 $dp[a][b][c][d]$ 表示安全区域左上角为 $(a,b)$，右下角为 $(c,d)$ ，在危险区域能救起的 robot 的最大数量 。

至于转移，预处理 Up[i][l][x] 表示第 i 列 [1,l] 的 robot 向上移动不超过 x 步能到达 E 的数量

上下左右四个方向类似 。

转移时考虑这个安全区域往里缩 ：

$dp[a][b][c][d]+?\to dp[a][b+1][c][d]$

上下左右四个方向同理 。

答案 $\max (dp[i][j][i][j]+1)(s[i][j]=o)$ 。因为最后一个 robot 一定是安全的 。

这题的状态和阶段太难想到了 。毋宁称之为构造dp题 。

Prefix Median

AGCAGCAGC