本质子序列个数
本质子序列个数
本文搬运自本人高中时期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 中不含） 第二条...
2021-11-14
【洛谷P2079 烛光晚餐】 题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552456.html 题目链接 看到什么价值的什么喜爱度的明显是背包。 然而题目还要考虑小明的感受，所以弄个二维费用背包。 设 dp(i,j,k)dp(i, j, k)dp(i,j,k) 为前 iii 道菜，用 jjj 元，且小明的喜爱程度为 kkk 时小红的最大喜爱度。 如果不选，则 dp(i,j,k)=dp(i−1,j,k)dp(i, j, k)=dp(i-1, j, k)dp(i,j,k)=dp(i−1,j,k)。 如果选，则 dp(i...
2022-01-18
数位DP总结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15818532.html 数位dp的引入 首先假设有一天，我们遇见一道题： 求在 [a,b][a,b][a,b] 的区间里，满足条件的数有多少个。 如果我们没学过数位dp，我们会打出这样一个暴力： 12for(i=a; i<=b; ++i) if(check(i)) ++ans; 这样的时间复杂度是 O(n×check的时间复杂度)O(n\times \text{check的时间复杂度})O(n×check的时间复杂度) 当 a,b...
2023-09-27
贪心+二分+DP+矩阵快速幂：CF461E
贪心+二分+DP+矩阵快速幂：CF461E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133316261 https://codeforces.com/contest/461/problem/E 第一步：捕捉题目信息 四种字符 →\to→ 矩阵 n≤1018→n\le 10^{18}\ton≤1018→ 矩阵快速幂 →\to→ dp 最小值最大 →\to→ 二分 第二步：分析性质 sss 未知？那如果已知怎么做，肯定是每次暴力选最长的。 ...
2024-09-11
[SDOI2010] 地精部落（简单DP）
[SDOI2010] 地精部落（简单dp） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142138324 https://www.luogu.com.cn/problem/P2467 一开始想错方向，小丑了 设 f(i,j,0/1)f(i,j,0/1)f(i,j,0/1) 表示还剩 iii 个，上一个在剩余数里面排名为 jjj ，之前是上升/下降的方案数，转移显然 滚一下前缀和就好 123456789101112131415161718192021222...
2022-04-28
【CF474D Flowers】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16203821.html 题目链接 题目 We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be r...