本质子序列个数
本质子序列个数
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885848
设为 结尾的方案数
假设每次遇到
之前的所有情况和空集都可以接
可以结合矩阵进行一些奇奇怪怪的操作
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-17
本质不同01序列DP方法
本质不同01序列dp方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885358 设 ggg 为本质不同方案， f0/1f_{0/1}f0/1 为以0/1结尾本质不同子序列的方案。假设遇到数字 iii fi′=gg′=2g−fif'_i=g\\g'=2g-f_i fi′=gg′=2g−fi 第一条式子： 对于原先每种情况都可以接或不接 iii ，不会重复，因为我们钦定必须加（ ggg 中包含空集， fff 中不含） 第二条...
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-08-10
容量很大体积很小的背包问题
容量很大体积很小的背包问题 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132216843 完全背包 https://www.luogu.com.cn/problem/P9140 多重背包 http://zhengruioi.com/problem/2620 值域大体积小，所以肯定是优先选性价比高的。 但是恰好的条件很难搞，记 mmm 为 maxwi\max w_imaxwi 的。 然后可以想象最后肯定是拿走一部分，再加入一部分。 然后在...
2022-04-26
【CF455A Boredom】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16195790.html 题目链接 题目 Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it. Given a sequence $ a $ consisting of $ n $ inte...
2023-12-16
李超线段树维护斜率DP：P4655
李超线段树维护斜率dp：P4655 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135036474 https://www.luogu.com.cn/problem/P4655 这东西长得就很像斜率优化的东西，但是不能用朴素斜率优化，因为横坐标不满足递增。 但我们可以直接用李超线段树维护即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...
2022-01-10
【CF6D Lizards and Basements 2】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15784843.html 题目链接 题目 This is simplified version of the problem used on the original contest. The original problem seems to have too difiicult solution. The constraints for input data have been reduced. Polycarp likes to play ...