本质子序列个数
本质子序列个数
本文搬运自本人高中时期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-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 的。 然后可以想象最后肯定是拿走一部分，再加入一部分。 然后在...
2023-12-20
二分+DP优化：CF1550E
二分+dp优化：CF1550E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135117074 https://www.luogu.com.cn/problem/CF1550E 一眼二分，然后有个朴素dp， f(i,2k)f(i,2^k)f(i,2k) 表示在 iii 位置满足已经存在 sss 是否可行。发现记录的值只有0 / 1，直接状态如dp， f(s)f(s)f(s) 表示满足 sss 的最前位置。 继续优化。状态明显不可以优化，只能优化转移了。这种...
2021-12-05
【Poj 1191 棋盘分割】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15646888.html 题目链接 题目 将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行) 原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。 均方差，其中平均值，xi为第i块矩形棋盘的总分。 请...
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...
2023-09-07
异或和大小比较类问题——抓住最高位：CF1863F
异或和大小比较类问题——抓住最高位：CF1863F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132629186 https://codeforces.com/contest/1863/problem/F 因为有等于，所以考虑异或和为0的合法区间，它可以随意切 现在考虑切开后左边大于右边，可以发现左右边最高位可以互相抵消，似乎不太可做？ 此时可以换个考虑，考虑大区间的异或和的最高位，这一位在左右两个区间 恰好 有一位为1，而为1的那个区间就是...