zcmimi's blog

arrow_back动态规划共96篇文章

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

点击跳转

f(i,j)表示前i个划分成j段最少的费用

我们设calc(l,r)表示[l,r]划分成一段的费用

f(i,j)=\min_{x=1}^i(f(x-1,j-1)+calc(x,i))

可以发现这个dp方程具有决策单调性

i<i',那么k_i\le k_{i'}(决策点)

把连续一段拆成两边更优x^2+y^2\le (x+y)^2(x,y\ge 0)

更巧的是w(l,r)可以用类似莫队的方法线性转移

这里采用分治的方法实现

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

点击跳转

单调队列优化dp

f[i]表示从1-i最多能选出的效率

枚举断点j,

f[i] = \max(f[j-1]+ \sum_{t=j+1}^i a[t])

但是直接这样的复杂度不可行

我们可以考虑用单调队列优化

f[i] = \max(f[j-1] - S_j) + S_i

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

点击跳转

tarjan找出强连通分量之后树形dp

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

点击跳转

解法1:

贪心

把深度大于2的都加到堆中

每次取出深度最大的点

从根结点往它父亲连边

然后把周围的节点标记为已经覆盖

解法2:

树形dp

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

点击跳转

f_i表示前i块土地

f_i=\min_{j=1}^{i-1}(f_j+maxw[j-1][i]\times maxh[j-1][i])

这样的话怎么想都没有办法优化

我们发现,如果一块土地被另一块土地所包含(即长和宽都比另一块土地小),

那么只需购买那另一块土地即可,于是我们可以据此筛掉其他的土地,

只剩下一些长度递减,宽度递增的土地

那么:

f_i=\min_{j=1}^{i-1}(f_j+l[j+1]\times w[i])

设任意0\le j<k<i,若从j转移比从k转移优,那么

f_j+l[j+1]\times w[i]\le f_k+l[k+1]\times w[i] \\ w[i](l[j+1]-l[k+1])\le f_k-f_j \\ w[i]\le \frac{f_k-f_j}{l[j+1]-l[k+1]}

维护一个下凸壳就完事了

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

点击跳转

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

f_i=\min_{j=0}^{i-1}(f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j))

设任意0\le j<k<ij转移比从k转移优,那么

f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j) \le f_k+s\times(w_n-w_k)+t_i\times(w_i-w_k) \\ t_i(w_k-w_j)\le f_k-f_j+s(w_j-w_k) \\ t_i\le \frac{f_k-f_j+s(w_j-w_k)}{w_k-w_j} \\ t_i+s\le \frac{f_k-f_j}{w_k-w_j}

维护个下凸壳就可以了

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

点击跳转

把节点按行排序

因为k很小,所以直接k^2dp就可以了

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

点击跳转

f[i][j]表示前i个数选了j个最多多少

f[i][j]=\max(f[i-1][j-1]+[a[i]=j],f[i-1][j]);

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

点击跳转

动态规划

逆向思维

用所有的减去不合法的

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

点击跳转

7/10
Search
search