zcmimi's blog

arrow_back动态规划共94篇文章

avatar
zc
2020-04-25 19:52:00
查看原题

点击跳转

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

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

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

f(i,k)=f(k+1,j)=1w(i,k)=w(k+1,j)时,合并即可

avatar
zc
2020-04-24 22:28:00
查看原题

点击跳转

avatar
zc
2020-02-27 22:12:00
查看原题

点击跳转

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

找零: 使用完全背包

avatar
zc
2020-02-27 21:36:00
查看原题

点击跳转

多重背包优化模板

avatar
zc
2020-02-16 18:54:00
查看原题

点击跳转

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

考虑怎么转移:

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

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

  2. 设另外b个插在同色木块中间

其中有a-b组满足插空放且不相邻

f[i,j]=\sum f[i-1,j-(c_i-a-b)]\times {c_i-1 \choose a-1} \times {j \choose b} \times{S_{i-1}+1-j \choose a-b}

{c_i-1 \choose a-1}表示a个的方案数

{j \choose b}表示b个的方案数

{S_{i-1}+1-j \choose a-b}表示a-b个插进去的方案

avatar
zc
2020-02-16 15:21:00
查看原题

点击跳转

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

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

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

直接枚举\mathcal{O(n^2k^2)}会超时,我们得想个办法优化

可以考虑用二维树状数组优化

优化为只需要两个树状数组

https://guodonglovesoi.blog.luogu.org/scoi2014-fang-bo-bo-di-yu-mi-tian

avatar
zc
2020-01-30 09:40:00
查看原题

点击跳转

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

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

  1. 这些新通道的代价和

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

    假设yx的某个子节点,x\leftrightarrow y会被统计(k-SZ_y)\times SZ_y次,

    (起点可以是y的子树中任一查询点,终点可以是y子树外的任一查询点,这样的话路径必然经过x\leftrightarrow y)

    那么贡献是(d_y-d_x)\times (k-SZ_y)\times SZ_y

  2. 这些新通道中代价最小/大的是多少

    有点类似树型dp求树的直径

    x的子树中最长的路径是: 子树中深度最大的查询点的深度+子树中深度次大的查询点的深度(若x是查询点则包括x\leftrightarrow x,深度为0)

    最短路径和上面的求法类似

套上虚树就可以解决这道题了

如果不懂的话就看代码咯

avatar
zc
2020-01-29 15:02:00
查看原题

点击跳转

avatar
zc
2020-01-29 08:06:00
查看原题

点击跳转

avatar
zc
2020-01-28 21:26:00
查看原题

点击跳转

2/10
Search
search