zcmimi's blog

arrow_back动态规划共96篇文章

avatar
zcmimi
2020-02-29

01背包

每个物品只能使用一次

普通多重背包

将可以用多次的物品拆为多个单次使用的物品

转化为01背包

二进制优化多重背包

但每个物品可以用的次数特别大的时候,如果还是直接拆很有可能会tle

[LG 1776 宝物筛选](https://www.luogu.com.c

avatar
zcmimi
2020-01-26

对于类似f_i=\min_{j=1}^{i-1}f_j+val(i,j)的方程

比如val(i,j)=a_i\times b_j,同时包含了i,j两个变量,

这样没法直接用单调队列

如果把val(i,j)展开能转化成$\frac{y{j1}-y{j2}}{x{j1}-x

avatar
zcmimi
2020-01-10

四边形不等式

定义

对于任意a_1\le a_2<b_1\le b_2,满足m[a_1,b_1]+m[a_2,b_2]\le m[a_1,b_2]+m[a_2,b_1]

那么m[i,j]满足四边形不等式

要证明m[i,j]满足四边形不等式可以用打表或数

avatar
zcmimi
2019-12-01

划分dp

题意

每组输入是两个整数nk(1\le n \le 50, 1 \le k \le n)

输出

对于输入的n,k;

第一行: 将n划分成若干正整数之和的方案数。

第二行: 将n划分成k个正整数之和的方案数。

第三行: 将n划分成最大

avatar
zc
2020-10-21 16:41:02

查看原题

点击跳转

解法一

最小权覆盖集 = 全集 - 最大权独立集

动态dp

只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷

解法二

倍增/树链剖分+树形dp

每次修改的两个点a,b构成一条链

可以链上连接的子树与链中间的点的结果不受修改影响,只有a,b的转移受影响,需要单独处理

那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护

这样只需要处理a,b

avatar
zc
2020-10-19 21:49:55

查看原题

点击跳转

f[sta]为死了的猪状态为sta时最少需要多少鸟

f[sta|line(i,j)]=\min(f[sta]+1)(line(i,j)表示经过i,j的抛物线能杀死的🐖的集合)

f[sta|(1<<i)]=\min(f[sta]+1)

优化:

若令x为满足sta\&(1<<(x-1))=0的最小正整数,则由sta扩展的转移的所有线都要经过x

avatar
zc
2020-10-19 19:55:41

查看原题

点击跳转

f(i,j,0),f(i,j,1)表示:

i个时间段,已经用了j个机会,选择c_i与选择d_i(换/不换教室)的最小期望

dis(i,j)表示i,j之间最短距离

转移方程:

f(i,j,0)=\min \begin{cases} f(i-1,j,0)+dis(c_{i-1},c_i)\\ \begin{aligned} f(i-1,j,1) &+dis(d_{i-1},c_i)\times k_{i-1}\\ &+dis(c_{i-1},c_i)\times(1-k_{i-1}) \end{aligned} \end{cases}

f(i,j,1)=\min \begin{cases} \begin{aligned} f(i-1,j-1,0) &+dis(c_{i-1},d_i)\times k_i\\ &+dis(c_{i-1},c_i)\times (1-k_i) \end{aligned}\\ \begin{aligned} f(i-1,j-1,1) &+dis(d_{i-1},d_i)\times k_{i-1}\times k_i\\ &+dis(c_{i-1},d_i)\times (1-k_{i-1})\times k_i\\ &+dis(d_{i-1},c_i)\times k_{i-1}\times (1-k_i)\\ &+dis(c_{i-1},c_i)\times (1-k_{i-1})\times (1-k_i)\\ \end{aligned} \end{cases}

avatar
zc
2020-10-17 11:25:38

查看原题

点击跳转

x构造一个矩阵满足a(i,j+1)=2a(i,j),a(i+1,j)=3a(i,j)

对于这个矩阵,我们不能选相邻的数,也就是说答案为不选相邻的数的方案数

这个矩阵长\log_2 n(不超过17),宽\log_3 n(不超过12),因此可以用状压dp解决

我们只需要对不是2,3倍数的数都构造一个矩阵就可以覆盖所有的数,容易发现每个矩阵互不相同,所以根据乘法原理把答案相乘即可

avatar
zc
2020-10-13 21:50:58

查看原题

点击跳转

很容易想出普通的dp

不过n \le 10^{18},所以要构造加速矩阵,使用矩阵快速幂

avatar
zc
2020-10-13 19:58:29

查看原题

点击跳转

f[i][j]表示用完前i个通配符,是否能匹配[1,j],

s为含通配符字符串,t为目标字符串,p_i为第i个通配符的位置

下文x|=y表示: 若y能,则x也能

若第i个通配符为*,*可以代替j之后的所有字符

那么f[i][j]|=f[i][j-1],也就是用*继续匹配下去(j-1位之后用*匹配)

s[p_i+1,p_{i+1}-1]=t[j+1,j+p_{i+1}-p_i-1],

那么f[i+1][j+(p_{i+1}-1)-(p_i+1)+1+[s[p_{i+1}]=?]]|=1

其中[s[p_{i+1}]='?']s[p_{i+1}]?时为1,否则为0

详见代码

1/10
Search
search