本质不同01序列DP方法
本质不同01序列dp方法
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885358
设 为本质不同方案， 为以0/1结尾本质不同子序列的方案。假设遇到数字
第一条式子：
对于原先每种情况都可以接或不接 ，不会重复，因为我们钦定必须加（ 中包含空集， 中不含）
第二条式子：
设
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-17
本质子序列个数
本质子序列个数 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885848 fif_ifi 设为 iii 结尾的方案数 假设每次遇到 kkk fk=∑fi+1f_k=\sum f_i+1fk=∑fi+1 之前的所有情况和空集都可以接 kkk 可以结合矩阵进行一些奇奇怪怪的操作
2023-09-17
数位DP+判定转状态：Loj #6274. 数字
数位dp+判定转状态：Loj #6274. 数字 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132950029 https://loj.ac/p/6274 和位运算有关，然后值域范围又非常大，位之间关联不大，显然考虑数位dp 然后有上下界限制，直接来个4维 然后每一位考虑，先满足or的性质，然后考虑and 发现有冲突只会是（1,0）和（0,1） 首先如果发生冲突，则要么无限制，要么上界为1，下界为0 所以某位0的以后不会受上界影响，某位为1以后不会受下界...
2023-12-26
建图+分类讨论+DP：CF704C
建图+分类讨论+dp：CF704C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135232777 https://vj.imken.moe/contest/599445#problem/C 我们直接建图，由于度数最多为2，要么是环，要么是点，要么是链。（对于操作1直接打tag即可） 对于链，我们直接 f(0/1,0/1)f(0/1,0/1)f(0/1,0/1) 表示上一位是啥，当前异或和为啥的方案数。如果是环，就破环成链，然后记一下第一个是啥。 然后就是...
2021-11-21
【P1108 低价购买】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15585466.html 题目链接 首先第一问很好求，就是求最长下降子序列，n⩽5000n\leqslant 5000n⩽5000，O(n2)O(n^2)O(n2) 暴力转移就行。 而这道题的难点就在于去重。 对于 iii 和 jjj（i>ji>ji>j），如果 ai=aja_i=a_jai=aj 且 dpi=dpjdp_i=dp_jdpi=dpj，说明他们是相同的，iii 的方案要清0，但是这里不能break！ 因为对...
2022-01-20
状压DP小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15825535.html 状压dp的引入 状压DP，是用二进制的性质来描述状态的一种DP。 对于状压dp，我们要先了解一下位运算。 位运算 x&y 与运算，101&110=100 x|y 或运算，100|101=101 x^y 异或运算，101^100=001 x<<1 左移运算 x>>1 右移运算 状压dp 先看一道题： 在 n×nn\times nn×n 的棋盘上放 kkk 个国王，国王可攻击相邻...
2023-09-27
DP维护概率算期望+DP状态大小分析+DP状态维护前缀和：CF494C
dp维护概率算期望+dp状态大小分析+dp状态维护前缀和：CF494C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133343917 https://www.luogu.com.cn/problem/CF494C 首先无交，先建树，然后上dp，三个优化 dp维护概率算期望 发现期望很难直接维护，直接维护某种值得概率，最后乘起来算期望 dp状态大小分析 发现这样子第二维会很大。但其最大值范围只在 [mx,mx+q][mx,mx+q][mx,mx+q] 内，...