zcmimi's blog

arrow_back区间dp共6篇文章

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
2019-12-21 19:47:00
查看原题

点击跳转

详见四边形不等式优化

最小值有单调性,可以使用四边形不等式优化

但是最大值没有

但是最大值有个性质:

一定是一直把其他石子合并到某堆石子

那么我们可以f[l][r]=\max(f[l][r-1],f[l+1,r])+S_r-S_{l-1}

相当于一直向左边的石子合并或右边

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

看了看数据范围,可以知道是状态压缩+区间dp

我们设f[i][j][t]表示[i,j]合并后状态为t获得的分数

f[i][j][t] = f[i][k][t'] + f[k+1][j][t''] (t'|t'' = t)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

区间dp

显然设f[i][j]表示[i,j]最小的表示方法

普通情况:

f[i][j] = \min(f[i][k]+f[k+1][j])

当我们找到循环节:

f[i][j] = \min(f[i][j],f[i][k] + 2 + \text{<循环节个数>})

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

好题

思路很妙

L[i][j]表示区间[i,j-1]作为j的左儿子是否合法

R[i][j]表示区间[i+1,j]作为i的右儿子是否合法

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先把连续的块缩成一个点

f[i][j]表示[i,j]全部涂成一种颜色最少要多少次

f[i][j] = \min(f[i+1][j],f[i][j-1])+1

c[i]==c[j],f[i][j]=f[i+1][j-1]+1

1/1
Search
search