zcmimi's blog

arrow_back动态规划共100篇文章

avatar
zcmimi
2020-11-14 21:09:40
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-12-02 17:48:25

查看原题

点击跳转

设有a1,b2

f_i为剩下i1的方案数

f_i=f_{i-1}+(i-1)\times f_{i-2}

接着考虑剩下2的情况

我们把2次交换的限制看成一次主动交换和一次被动交换

那我们就可以让b2都先使用一次主动交换

那么第一个2可以从n个中选一个

第二个2可以从n-1中选一个

第三个2可以从n-2中选一个

...以此类推

这样b次交换后会剩下正好a1

ans=f_a\times \prod_{i=1}^b (n-i+1)

avatar
zc
2020-12-01 10:42:49

查看原题

点击跳转

f_i=f_j+\max(a_{j+1},a_{j+2},\dots,a_i), s_i-s_j\le m

对于转移方程可行的ja_{j+1}\le \max(a_{j+2},\dots,a_i),f_j+\max(a_{j+1},\dots,a_i)f_{j+1}+\max(a_{j+2},\dots,a_i)后半段相同,f_j\le f_{j+1},所以前者更优

推广可得最优转移一定在a_{q_1}>a_{q_2}>a_{q_3}>a_{q_4}>\dots>a_{q_j}

f_{a_{q_j}}+a_{q_{j+1}}取得(对于a_{q_1},有f_{st}+a_{q_1},st是最大的使a_{st}+\dots+a_i>m

维护一个可查询最大值的单调队列

维护一个中点,向两端维护单调栈,如果左右端点超过中点就重构单调栈

avatar
zc
2020-11-25 09:44:26

查看原题

点击跳转

avatar
zc
2020-10-27 20:44:01

查看原题

点击跳转

解法一

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

动态dp

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

解法二

倍增/树链剖分+树形dp

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

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

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

这样只需要处理a,b

f(i,0/1)表示i选/不选,以i为根的子树的最小代价,g(i,0/1)表示整棵树除了以i为根的子树的最小代价,可以通过树形dp求出

F(i,j,0/1,0/1)表示i选/不选,i2^j级祖先选/不选,i子树到ii2^j级祖先子树的最小代价,可以倍增求出

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

1/10
Search
search