本质不同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 可以结合矩阵进行一些奇奇怪怪的操作
2021-11-22
【NOIP2021 数列】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15590387.html 题目链接 首先dp得从低位向高位枚举，因为高位无论如果使用 2ai2^{a_i}2ai 都对低位二进制1的个数无影响，满足dp的无后效性。 设 dp(k,i,x,y)dp(k, i, x, y)dp(k,i,x,y) 为 SSS 从低的高二进制的前 kkk 位中，用了数列 aaa 的前 iii 项，且此时 SSS 中共有 xxx 个二进制位为1，第 i+1i+1i+1 位进了 yyy 过去。 则： dp(k,i,x,y...
2024-09-09
P2605 [ZJOI2010] 基站选址（线段树优化DP）
P2605 [ZJOI2010] 基站选址（线段树优化dp） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142056966 https://www.luogu.com.cn/problem/P2605 看错题几次，无语了 我们设一个 f(i,j)f(i,j)f(i,j) 表示第 jjj 个基站在 iii ，然后对于一个 [l,r][l,r][l,r] ，如果里面建了基站就搞定，建不了就需要 www 的代价。 [l,r][l,r][l,r] 离散化后按 r...
2021-11-24
【NOIP2021 方差】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15598937.html 题目链接 Part A 式子化简 首先题目要求的式子就是 n2n^2n2 乘上 1n∑i=1n(ai−aˉ)2\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2n1∑i=1n(ai−aˉ)2，其中 aˉ=1n∑i=1nai\bar a=\frac{1}{n}\sum_{i=1}^n a_iaˉ=n1∑i=1nai。 我们把这三合在一起也就是： n2×1n∑i=1n(ai−1n∑j=1n...
2021-12-04
2021.12.4 上课笔记（DP专题）
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640975.html cf1110e 给定一个序列 A{}，每次可以选择 1 < i < N 的一个元素，更新 Ai=Ai−1+Ai+1−AiA_i = A_{i-1} + A_{i+1} - A_iAi=Ai−1+Ai+1−Ai。 问是否可以是序列 A{} 变化得到序列 B{}。 判断差分、首项是否相等即可。 poj1191 题面 对于式子中一些没影响的东西去掉，原式就是求 ∑n2a2−n(∑aj)2\sum n^2 a...
2023-10-20
wqs二分+斜率优化：1019T4 / P9338
wqs二分+斜率优化：1019T4 / P9338 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133955885 https://www.luogu.com.cn/problem/P9338 考虑暴力前 iii 个分 jjj 段 fi,k=fj−1,k−1+gj,if_{i,k}=f_{j-1,k-1}+g_{j,i}fi,k=fj−1,k−1+gj,i ， O(n3)O(n^3)O(n3) 然后划分段数，段数显然越多越优，那么就上wqs二分， O...