对于DP颜色类问题的切换方法：P9561
对于dp颜色类问题的切换方法：P9561
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471731
对于dp颜色类问题的切换方法
两种颜色为例，一般情况下 可以由 在某些情况下转移
但从0到0的过程中，对于 前的1，可能 满足，但 不满足
此时可以考虑0只从1转移，1只从0转移，对于新的0，我们除了统计当前dp值，我们还要维护之前1的转移值
常用于线段+颜色类dp问题
题：P9561
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2022-02-15
【一本通OJ 1603：绿色通道】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15897506.html 题目链接 题目 高二数学《绿色通道》总共有 nnn 道题目要抄，编号 1…n1\ldots n1…n，抄第 iii 题要花 aia_iai 分钟。小 Y 决定只用不超过 ttt 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。 现在，小 Y 想知道他在这 ttt 分钟内写哪...
2021-11-24
【P1270 “访问”美术馆】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=maxy∈xmaxi=0smaxj=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...
2021-11-18
【P2344 [USACO11FEB]Generic Cow Protests G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574309.html 题目链接 首先朴素dp不用讲，设 dpidp_idpi 表示前 iii 个数划分的总方案数，SiS_iSi 表示前 iii 个数的和。 dpi=∑j=0i−1dpj (Si−Sj⩾0)dp_i=\sum_{j=0}^{i-1}dp_j\,\,\,(S_i-S_j\geqslant 0) dpi=j=0∑i−1dpj(Si−Sj⩾0) 其中 dp0=1dp_0=1dp0=1。 可是这样的时间复杂度为 O...
2023-08-08
通过数据结构维护数论分块结果：ZR2609
通过数据结构维护数论分块结果：ZR2609 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132178041 http://zhengruioi.com/problem/2609 对于 这类东西，应该是自然反应，枚举个 aia_iai ，然后数论分块，这里是 O(nn)O(n\sqrt n)O(nn) 然后会在纸上推一大轮（结论忘了）推出 xxx 的合法区间 [l,r][l,r][l,r] ，然后就是判断 aj∈[l,r]a_j\in[l,r]aj∈...
2021-11-15
【2021牛客网赛前第二场普及模拟赛C数数】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558033.html 题目大意 我们称一个集合 S=(x1,y1),(x2,y2),…,(xk,yk)S={(x_1, y_1), (x_2, y_2), … , (x_k, y_k)}S=(x1,y1),(x2,y2),…,(xk,yk) 是好的，当且仅当把它们按照 yiy_iyi 降序排序后满足： 对于所有满足 3≤j≤k3 ≤ j ≤ k3≤j≤k 的 jjj，有 xj−2<xj<xj−1x_j−2 <...
2022-02-17
【一本通OJ 1601：【例 5】Banknotes】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905471.html 题目链接 题目 原题来自：POI 2005 Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 nnn 种面值的硬币，面值分别为 b1,b2,⋯ ,bnb_1, b_2,\cdots , b_nb1,b2,⋯,bn 。但是每种硬币有数量限制，现在我们想要凑出面值 kkk，求最少要用多少个硬币。 思路 首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。 同时，我们也可以把...