可删除背包（计数类）： P4141
可删除背包（计数类）： P4141
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028419
https://www.luogu.com.cn/problem/P4141
看完第一眼想到打分治，然后记得以前打abc时好像见到过一种可撤销背包。
使用条件：
-
计数类，非最优性问题
-
物品之间顺序无影响
因此我们直接撤销是对的
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2024-01-15
原根 + 背包 + bitset优化 + 二进制分组：0115B
原根 + 背包 + bitset优化 + 二进制分组：0115B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135609260 http://47.92.197.167:5283/contest/451/problem/2 原根： g1,…,gp−1g^1,\dots,g^{p-1}g1,…,gp−1 在 mod p\bmod pmodp 意义下取遍 1∼p−11\sim p-11∼p−1 。在 ppp 为质数时， ggg 不超过 p14p^{\fr...
2022-09-11
多重背包优化小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16576747.html 普通多重背包 外层枚举哪个包，中层枚举容量，内存枚举数量 1234for(i=1; i<=n; ++i) for(j=m; j>=0; --j) for(k=1; k*w[i]<=j && j<=s[i]; ++k) f[j]=max(f[j], f[j-k*w[i]]+k*v[i]); 二进制优化 相当于把每个包拆成 logloglog 个包然后分别01背包 123456...
2023-09-24
可删除背包（计数类）=＞转移数组进行展开：ABC321F
可删除背包（计数类）=＞转移数组进行展开：ABC321F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133219375 https://atcoder.jp/contests/abc321/tasks/abc321_f 还真没见过这个套路，呜呜┭┮﹏┭┮ 首先加就正常加，从后往前 但删的话应该是从前往后减 为什么呢？ 先写一下自己的理解，加要从后往前加是为了防止加多次 减的话为了保证每个被删的数只减一次，应该从前往后。 考虑前 iii 个已经被还原了，那...
2021-12-08
【CF577B Modulo Sum】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15664786.html 题目链接 题目 You are given a sequence of numbers a1, a2, …, an, and a number m. Check if it is possible to choose a non-empty subsequence aij such that the sum of numbers in this subsequence is divisible by m. 给出 111 ...
2023-12-16
背包+根号分治：loj6089
背包+根号分治：loj6089 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135032303 https://loj.ac/p/6089 考虑根号分治，前面是个多重背包，直接分组部分和优化。 然后后面是个完全背包，直接做容易炸，但直接上整数划分dp即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...
2021-11-18
【P2340 [USACO03FALL]Cow Exhibition G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15573796.html 题目链接 一道很好的01背包变形题。 首先看一眼题很明显可以发现是背包。 此题我当时的第一反应是二维费用背包，然而会TLE+MLE，于是打开题解思考01背包做法。 设 dpidp_idpi 代表智商和为 iii 时情商的最大值。 dpi=maxj=1n(dpi−sj+fj)dp_i=\max_{j=1}^n(dp_{i-s_j}+f_j) dpi=j=1maxn(dpi−sj+fj) 经典的01背包转移。 ...