cdq优化背包转移：GYM104531I
cdq优化背包转移：GYM104531I
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132549832
https://codeforces.com/gym/104531/problem/I
转化部分： 关于 括号序列与问号 问题的一类处理方法
发现一个区间 合法要满足以下条件：
最后一个很好搞。前3个就是个cdq形式。
第一个拿来排序，后面对于黑白点分别以不同的形式（数）存在。
dp类cdq中，应先dp左，再计算左对右，最后计算右，这样可以保证cdq顺序不出现问题
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-27
DP维护概率算期望+DP状态大小分析+DP状态维护前缀和：CF494C
dp维护概率算期望+dp状态大小分析+dp状态维护前缀和：CF494C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133343917 https://www.luogu.com.cn/problem/CF494C 首先无交，先建树，然后上dp，三个优化 dp维护概率算期望 发现期望很难直接维护，直接维护某种值得概率，最后乘起来算期望 dp状态大小分析 发现这样子第二维会很大。但其最大值范围只在 [mx,mx+q][mx,mx+q][mx,mx+q] 内，...
2023-09-22
线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3
线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133175632 http://cplusoj.com/d/senior/p/SS230922C 首先有个贪心，按长度从大往小选，是错的 然后有个dp，按左端点排完后选连续段，也是错的 但把上面两个结合起来，还是错的 然后此时错的有个共性，就是存在区间包含关系 然后我们把区间包含关系去掉，另外统计贡献，那样是对的 只不过超时而已 然后发...
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-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 的第一个儿子转移过来...
2023-08-27
wqs二分
wqs二分 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132522464 前提：答案满足凸性 题目类似为 nnn 个里面选 mmm 个求某种代价，暴力二维dp复杂度大，但容易计算不限制选的次数。 由于不限制选的次数，所以给选一个东西给一个代价 vvv ，然后判断最后选了多少个，再来调整这个 vvv 要方便调整这个 vvv ，就要二分。而能二分，说明具有单调性。把 vvv 视为斜率，斜率有单调性，所以原函数具有凸性。