menu zcmimi's blog

arrow_back 动态规划

f(i,j,0/1,0/1)表示第i轮的第j场,你是否是胜利者的粉丝,是否是失败者的粉丝

可以发现轮数有点像堆,如果轮数从0开始编号,第i轮的第j场由第i-1轮的第$2

zc
2020-05-05 09:31

f_{i,j}表示前i个点,第i个点的覆盖状态为j(j8位二进制数)

```cpp

include<bits/stdc++.h>

define gc getchar

zc
2020-04-26 16:20

看到n\le 500容易想到是区间dp

f(i,j)[i,j]合并后的最小长度,w(i,j)为合并后的和

$f(i,j)=\min\left{ f(i,k)+f(k+1,j)

zc
2020-04-25 19:52

```cpp

include<bits/stdc++.h>

define fur(i,x,y) for(int i(x);i<=y;++i)

define fl(i,x) for(int i(h

zc
2020-04-24 22:28

01背包

每个物品只能使用一次

普通多重背包

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

转化为01背包

二进制优化多重背包

但每个物品可以用的次数特别大的时候,如果还是直

zcmimi
2020-02-29

能凑出的钱: 使用多重背包(二进制优化)

找零: 使用完全背包 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optim
zc
2020-02-27 22:12

多重背包优化模板 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __
zc
2020-02-27 21:36

f[i,j]表示用完了前i种油漆,有j对相邻且同色的木块

考虑怎么转移:

要将第i种颜色的木块分两种情况插入:

  1. 设其中a个插到之前弄好的木块中间(无序)

2

zc
2020-02-16 18:54

f(i,k)表示前i位置,操作k次,最多剩下多少玉米

每一次的拔高操作区间右端点一定是最右边的玉米

$f(i,k)=max_{j<i}(f(j,k-t))+1,a_i+t

zc
2020-02-16 15:21

先来考虑普通的树型dp怎么做

SZ_x表示x的子树中有多少个查询点,d_x表示x的深度

  1. 这些新通道的代价和

    考虑每条边要被统计多少次:

    假设y是$

zc
2020-01-30 09:40
1 / 9
Search
search