改变枚举顺序二分斜率时考虑斜率单调性来去掉log：0111A
改变枚举顺序二分斜率时考虑斜率单调性来去掉log：0111A
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135540204
<47.92.197.167:5283/contest/447/problem/1>
考虑区间dp，然后每个点维护下凸壳，转移时在凸壳上二分
这样子是带log的。考虑区间dp时改变枚举顺序，就可以满足斜率递增，不用二分了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-30
贪心找性质+DP表示+矩阵表示+线段树维护：CF573D
贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...
2021-11-17
【P2339 [USACO04OPEN]Turning in Homework G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15570096.html 题目链接 先按作业的提交地点排序。 设 dp(l,r,0/1)dp(l, r, 0/1)dp(l,r,0/1) 为还剩 [l,r][l, r][l,r] 的作业没交，且下一步交 l(0),r(1)l(0), r(1)l(0),r(1) 的最小步数。 显然： dp(l,r,0)=min(max(dp(l−1,r,0)+∣al−1−al∣, tl), max(dp(l,r+1,1)+∣ar+1−al∣, tl))dp(...
2023-09-27
博弈论（奇偶考虑法）+计数+DP（判定转DP）：CF838C
博弈论（奇偶考虑法）+计数+DP（判定转dp）：CF838C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133362167 首先题目有博弈，先分析一波最优策略（步骤：分析性质）。 两个人，所以显然考虑奇偶考虑法+递归考虑。 首先删就是使子问题-1，重新排列是在当前子问题里的。 一个串的排列是有限的，所以这里就可以上奇偶考虑法。如果有偶数种串，则必然是后手先“被迫“进入子问题（要算上初始情况） 考虑假设法：我们可以先假设进入子问题： 必赢。先手进！ ...
2023-08-11
对平移类DP用数据结构优化：ZR2617
对平移类dp用数据结构优化：ZR2617 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132240791 http://zhengruioi.com/problem/2617 对于此类dp式子： dpi,j=∑dpk,j−w(k,i)dp_{i,j}=\sum dp_{k,j-w(k,i)} dpi,j=∑dpk,j−w(k,i) 暴力计算为 O(n3)O(n^3)O(n3) ，但如果 w(j,i)w(j,i)w(j,i) 在 w(j,i−1)w(j,...
2022-01-07
【P6191 [USACO09FEB]Bulls And Cows S】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15774893.html 题目链接 题目 一年一度的展会要来临了，Farmer John 想要把 NNN（1≤N≤100,0001 \leq N \leq 100,0001≤N≤100,000）只奶牛和公牛安排在单独的一行中。 John 发现最近公牛们非常好斗；假如两只公牛在这一行中靠的太近，他们就会吵架，以至于斗殴，破坏这和谐的环境。 John 非常的足智多谋，他计算出任何两只公牛之间至少要有 KKK（0≤K<N0 \leq K \lt ...
2022-01-12
【P4551 最长异或路径】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15792154.html 题目链接 题目 给定一棵 nnn 个点的带权树，结点下标从 111 开始到 nnn。寻找树中找两个结点，求最长的异或路径。 异或路径指的是指两个结点之间唯一路径上的所有边权的异或 思路 预处理每个点到根节点路劲的异或和，建一棵01trie树。 对于每个节点，在trie树上找离它最远的节点，最后取个 max\maxmax 值即可。 总结 这道题应该也算两个经典问题的集合吧？ 首先求树上两个节点之间路径的异或和，这是一个非...