本质不同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 可以结合矩阵进行一些奇奇怪怪的操作
2022-01-14
【P2015 二叉苹果树】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15802114.html 题目链接 题目 有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点） 这棵树共有 NNN 个结点（叶子点或者树枝分叉点），编号为 1∼N1 \sim N1∼N，树根编号一定是 111。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 444 个树枝的树： 123452 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。...
2026-09-26
近期几道ABC的G题总结（473 - 476 ）
近期几道ABC的G题总结 ABC476G：数位dp + 分治 + 贪心 先从分治的角度考虑两个区间怎么合并 我们考虑对于一个区间，我们如果从合并的角度来说，只关心每个上升子序列开头和结尾1的数量。所以这本质可以用两个数组来存。aia_iai 表示开头popcount为 iii 有多少个子序列，bib_ibi 代表结尾。中间怎么连不重要。 现在考虑两个区间合并。显然从贪心的角度考虑，我们希望用 b1i→a2jb_{1i}\to a_{2j}b1i→a2j 尽可能多 (i<ji<ji<j)，那直接暴力贪心匹配即可。 我们现在回到原题，考虑数位dp。f(i,0/1,...
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，求最少要用多少个硬币。 思路 首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。 同时，我们也可以把...
2024-10-07
1006C简单题（计数式子的组合意义 + DP式子联立）
1006C简单题（计数式子的组合意义 + dp式子联立） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142740338 http://cplusoj.com/d/senior/p/SS241006C 对于这个式子，我们可以从它的组合意义入手。 假设我们有 n+1n+1n+1 个白球要染色，中间有一个绿球，绿球左边有 aaa 个红球，右边有 bbb 球。染完后绿球左边每个白球有 xxx 的贡献，右边每个白球有 yyy 的贡献。 但接下来怎么做呢？这列出来...
2022-06-11
【CF1512F Education】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16365234.html 题目链接 题目 有一个长度为 nnn 的数组 aaa 和一个长度为 n−1n−1n−1 的数组 bbb，初始位置为 pos=1pos=1pos=1，每一天可以选择得到 aposa_{pos}apos元钱，或者花费 bposb_{pos}bpos元钱（钱数不能为负）使得 pos←pos+1pos\leftarrow pos+1pos←pos+1 现在希望买一台 ccc 元的电脑，最少需要多少天。 Polycarp is...