DP答案和状态互换 || 多询问类DP转倍增/二分优化：CF1175E
dp答案和状态互换 || 多询问类dp转倍增/二分优化：CF1175E
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132571504
https://www.luogu.com.cn/problem/CF1175E
Trick 1
按照正常套路 为到达 （限制）最少多少条（答案），其实可以转化为 用 条（限制）最远可以到达哪里（答案）
对于难以解决的dp，可以尝试把状态和答案互换，观察是否有更好的解决方法
Trick 2
发现 很大，但满足可合并性，直接套倍增上去。处理时倍增，查询时也倍增
适合与查询有关的dp类题目。此类题目一般是预处理一些东西，询问时再求一些东西。可以为倍增/二分等方法。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-22
线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3
线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133175632 http://cplusoj.com/d/senior/p/SS230922C 首先有个贪心，按长度从大往小选，是错的 然后有个dp，按左端点排完后选连续段，也是错的 但把上面两个结合起来，还是错的 然后此时错的有个共性，就是存在区间包含关系 然后我们把区间包含关系去掉，另外统计贡献，那样是对的 只不过超时而已 然后发...
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-09-27
图论+博弈论上DP：CF536D
图论+博弈论上dp：CF536D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133364509 此题其实比较板，只是我没看出来 首先肯定要跑个最短路，然后发现可以离散化把值域缩小 然后 nnn 很小，直接暴力列个 n2n^2n2 dp。 转移要注意的是必须从大往小dp。从小到大会产生后效性。 然后拿个双指针优化下转移就行。 123456789101112131415161718192021222324252627282930313233343536373...
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-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-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 的第一个儿子转移过来...