wqs二分
wqs二分
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132522464
前提：答案满足凸性
题目类似为 个里面选 个求某种代价，暴力二维dp复杂度大，但容易计算不限制选的次数。
由于不限制选的次数，所以给选一个东西给一个代价 ，然后判断最后选了多少个，再来调整这个
要方便调整这个 ，就要二分。而能二分，说明具有单调性。把 视为斜率，斜率有单调性，所以原函数具有凸性。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-10
超长序列计数从值域入手（判定转状态）+分析DP状态数量：arc146_e
超长序列计数从值域入手（判定转状态）+分析dp状态数量：arc146_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132794937 https://atcoder.jp/contests/arc146/tasks/arc146_e Trick1 超长序列从值域入手（判定转状态） 通过绝对值的条件，其实我们可以从小到大放每个数。 对于两个相邻的同样数 iii ，他们之间必须放 i+1i+1i+1 因此可以设计 dp[i][j][0/1/2]dp[i][...
2026-07-09
一些动态规划的优化算法：斜率优化、四边形不等式、Slope Trick、wqs二分
一些动态规划的优化算法：斜率优化、四边形不等式、Slope Trick、wqs二分 斜率优化 考虑我们求解的问题可以简化为： fi=min(fj−j×ai)f_i=\min(f_j-j\times a_i) fi=min(fj−j×ai) 令 fi=b,fj=y,ai=kf_i=b,f_j=y,a_i=kfi=b,fj=y,ai=k，则： b=y−kx⇒y=kx+bb=y-kx\\ \Rightarrow y = kx + b b=y−kx⇒y=kx+b 其中 (x,y)(x,y)(x,y) 是本来就有的点（而且有很多个，均为备选项），bbb 为我们要求的东西，我们希望 b...
2023-08-29
DP答案和状态互换 || 多询问类DP转倍增/二分优化：CF1175E
dp答案和状态互换 || 多询问类dp转倍增/二分优化：CF1175E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132571504 https://www.luogu.com.cn/problem/CF1175E Trick 1 按照正常套路 dpidp_idpi 为到达 iii （限制）最少多少条（答案），其实可以转化为 dpidp_idpi 用 iii 条（限制）最远可以到达哪里（答案） 对于难以解决的dp，可以尝试把状态和答案互换，观察是否...
2023-09-22
线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3
线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133175632 http://cplusoj.com/d/senior/p/SS230922C 首先有个贪心，按长度从大往小选，是错的 然后有个dp，按左端点排完后选连续段，也是错的 但把上面两个结合起来，还是错的 然后此时错的有个共性，就是存在区间包含关系 然后我们把区间包含关系去掉，另外统计贡献，那样是对的 只不过超时而已 然后发...
2023-09-27
图论+博弈论上DP：CF536D
图论+博弈论上dp：CF536D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133364509 此题其实比较板，只是我没看出来 首先肯定要跑个最短路，然后发现可以离散化把值域缩小 然后 nnn 很小，直接暴力列个 n2n^2n2 dp。 转移要注意的是必须从大往小dp。从小到大会产生后效性。 然后拿个双指针优化下转移就行。 123456789101112131415161718192021222324252627282930313233343536373...
2023-09-23
点分治维护DP+连通块上新型DP思路+乘积方面进行根号DP：0922T4
点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp：0922T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133217931 首先连通块，所以点分治肯定是 Trick1 钦定选根的连通块dp 对于钦定选根的连通块dp，有一种常见思路 先对原树求其dfn序，按dfn序 倒序 求解 具体的，对于当前点 iii （注意这里都是指dfn序），我们可以钦定 iii 是否选 如果 iii 选，就由 i+1i+1i+1 ，也就是 iii 的第一个儿子转移过来...