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][...
2023-09-12
判定转状态+序列问题上树形DP：0909T3
判定转状态+序列问题上树形dp：0909T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132796834 考虑没有括号怎么做。 对于这类+*表达式求值问题，正常思考的dp是状态 O(n)O(n)O(n) ，总共为 O(n2)O(n^2)O(n2) 的 但其实可以对于每个dp记录两个值，分别为答案dp，和后面的乘积和g 如果接乘号，就是 [j](dp,g)→[j](dp+g(i−1),gi)[j](dp,g)\to[j](dp+g(i-1),gi)[j]...
2023-08-27
二分队列+决策单调性优化DP：P6246
二分队列+决策单调性优化dp：P6246 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132522515 https://www.luogu.com.cn/problem/P6246 决策单调性 若 dpidp_idpi 由 jjj 转移，则 dpi+1dp_{i+1}dpi+1 转移点 kkk 满足 k≥jk\ge jk≥j 发现决策点满足单调，但遍历的点不满足单调，不能用双指针，考虑二分队列。 二分队列 假设前 iii 个已定，只考虑从前转移到后...
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 的第一个儿子转移过来...
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...