山东大学_闫立峰

动态规划

ccsp(1) 图论(1) 并行计算(3) 数据结构(2) 杂(2) 网络流(1)

/ 注册

全部文章 / 动态规划（共3篇）

动态规划复习

1.背包 https://blog.csdn.net/yandaoqiusheng/article/details/84782655 这个博客基本总结的比较全了。 2.斜率优化 HDU 3507 暴力 f[i]=min{f[j]+s[i]^2+s[j]^2-s[i]*s[j]+W} f[i]=f[j...

2019-10-19

0 521

2019牛客国庆集训派对day3（被学弟吊锤记）

这场好搞笑啊，现在想起来还是想笑/xk 简单写一下G题蛮好的一道状压题。看数据范围八成就是n*2^n的状压了，先盲猜一下状态dp[S]，表示放好的数的下标状态为S的min值，可以看出，我们可以任意顺序把数放到序列里，只要保证他们的贡献不少就可以了。然后看到比较烦人的绝对值，就想办法扔掉它，方法就是...

2019-10-04

0 557

2019银川网络赛G（树形背包的一点优化）

这题一开始有了nkk的dp 然后一看肯定超时啊但是感觉跑不满听学长说有一种优化可以降到nk 学了一下不难理解但是具体的证明可能麻烦一点具体参考这个博客https://blog.csdn.net/lyd_7_29/article/details/79854245 #include<bit...

2019-09-05

0 376