Table of Contents
- 概述：
- 第一题：P1164 小A点菜
- 第二题：P2871 [USACO07DEC] Charm Bracelet S
- 第三题：P2925 [USACO08DEC] Hay For Sale S
- 第四题：P4141 消失之物 （难度：提高-）
- 今日总结：
P.S.:挑战3个月达省一的第12天，目前阶段：还是TMD 动态规划之背包问题；
欢迎收看今天的爆0日志：
概述：
完成了4题
写了一篇题解
修理了一下我的kali linux和主系统的emacs
第一题：P1164 小A点菜
题目：
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
## 题目描述
不过 uim 由于买了一些书，口袋里只剩 \(M\) 元 \((0 < M \le 10000)\)。
餐馆虽低端，但是菜品种类不少，有 \(N\) 种 \((1 \le N \le 100)\)，第 \(i\) 种卖 \(a_i\) 元 \((0 < a_i \le 1000)\)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 \(1\) 秒。
## 输入格式
第一行两个整数 \(N\) 和 \(M\)，分别表示菜品种类和 uim 身上的钱数。
第二行 \(N\) 个正整数 \(a_i\)（可能有重复），用空格隔开，分别表示每种菜的价格。
## 输出格式
一个正整数，表示点菜方案数，保证答案的范围在 \([0,2^{31}-1]\) 之内（不超过 C/C++的 int 范围）。
## 说明/提示
2020.8.29，增添一组 hack 数据 by @yummy
解题过程：
R 这道题跟我们之前做的所有背包问题都不太一样，这次是计数背包；
T 我们需要重新设计dp数组和状态转移方程；
T 对于dp数组的定义： \(dp_v\) 代表正好花完v元的方案数；
T 状态划分：买i、不买i；
T 转移方程： \(dp_v = dp_v + dp_{v-w_i}\) ;
T 解释一下： \(dp_v\) 由不买（即 \(dp_v\) ）和买（即 \(dp_{v-w_i}\) ）转移来，
更具体的说，不买时，方案数和到 \(i-1\) 为止的方案数一致，若买，方案数和 到 \(i-1\) 为止时背包容量为 \(v-w_i\) 时一致（因为要空出物品i的重量）；
T 初始化： i为0时（我们的物品编号为1-n），相当于没有任何物品，此时的方案数 \(dp_0 = 1\) （注意，仅容量为0时值为1，其余情况均不可能填满，为0）;
E 至此，分析完成，我们开始编写;
E 那么，最终用时21min，AC；
T 话说回来，他说的Hack数据跑哪去了？？？
第二题：P2871 [USACO07DEC] Charm Bracelet S
题目：
有 \(N\) 件物品和一个容量为 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，价值是 \(D_i\)。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
## 输入格式
第一行：物品个数 \(N\) 和背包大小 \(M\)。
第二行至第 \(N+1\) 行：第 \(i\) 个物品的重量 \(W_i\) 和价值 \(D_i\)。
## 输出格式
输出一行最大价值
## 说明/提示
\(1 \le N \le 3402\)，\(1 \le M \le 12880\)，\(1 \le W_i \le 400\)，\(1 \le D \le 100\)。
解题过程：
R 好吧，又遇到水题了，不过正好练练我的速度；
T 表示一下对题目的尊重，我们仍然认真的看一遍：给定物品和背包，求出最大价值，没什么问题
T 再看一下数据范围：3402件物品，12880的背包（这个确实有点大了，不过128M的内存限制，一维dp也没什么问题）；
E 我们开始干；
E 最终用时：2min28s AC，拿捏了也是；
第三题：P2925 [USACO08DEC] Hay For Sale S
题目描述
农民 John 面临一个很可怕的事，因为防范力度不大所以他存储的所有稻草都被蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，John 拉着他的马车到农民 Don 的农场中买一些稻草给奶牛过冬。已知 John 的马车可以装的下 \(C(1\le C\le5\times10^4)\) 立方的稻草。
农民 Don 有 \(H(1\le H\le5\times10^3)\) 捆体积不同的稻草可供购买，每一捆稻草有它自己的体积 \(V_i(1\le V_i\le C)\)。面对这些稻草 John 认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。
现在给定马车的最大容积 \(C\) 和每一捆稻草的体积 \(V_i\)，John 如何在不超过马车最大容积的情况下买到最大体积的稻草？他不可以把一捆稻草分开来买。
## 输入格式
第一行两个整数，分别为 \(C\) 和 \(H\)。
第 \(2\) 到 \(H+1\) 行:每一行一个整数代表第 \(i\) 捆稻草的体积 \(V_i\)。
## 输出格式
一个整数，为 John 能买到的稻草的体积。
解题过程：
R 仍然是基本的01背包问题，不过，少了个价值；
T 所以这就成了这道题唯一的 需要动点脑子的 不是很人机的地方；
T 我们只需要手动构造令价值与重量相等即可；
P 我们确认一下数据范围：物品种类：5000，背包大小：50000；
E 开始编写
T 最终用时：5min，AC
第四题：P4141 消失之物 （难度：提高-）
题目描述：
ftiasch 有 \(n\) 个物品, 体积分别是 \(w_1,w_2,\dots,w_n\)。由于她的疏忽，第 \(i\) 个物品丢失了。
“要使用剩下的 \(n-1\) 物品装满容积为 \(x\) 的背包，有几种方法呢？”——这是经典的问题了。
她把答案记为 \(\text{cnt}(i,x)\) ，想要得到所有\(i \in [1,n]\), \(x \in [1,m]\) 的 \(\text{cnt}(i,x)\) 表格。
## 输入格式
第一行两个整数 \(n,m\)，表示物品的数量和最大的容积。
第二行 \(n\) 个整数 \(w_1,w_2,\dots,w_n\)，表示每个物品的体积。
## 输出格式
输出一个 \(n \times m\) 的矩阵，表示 \(\text{cnt}(i,x)\) 的**末位数字**。
## 输入输出样例 #1
### 输入 #1
```
3 2
1 1 2
```
### 输出 #1
```
11
11
21
```
## 说明/提示
【数据范围】
对于 \(100\%\) 的数据，\(1\le n,m \le 2000\)，且 \(1\le w_i\le 2000\)。
【样例解释】
如果物品 3 丢失的话，只有一种方法装满容量是 2 的背包，即选择物品 1 和物品 2。
—
\(\text{upd 2023.8.11}\)：新增加五组 Hack 数据。
解题过程：
R 我们简化一下题目：给出n个物品和一个容量为m背包，但是物品和背包容量可变，具体来讲，物品个数为n-1（也就是说，其中一个不可用），背包容量为1-m，
给出每种情况下装满背包的方案数，输出n*m的矩阵，其中每个元素为方案数的个位数；
T 那么具体而言，我们需要解决以下几个子任务：
- 1.给定一个函数 \(solve(x,v)\)，每次指定一个物品x不计入计算过程，返回方案数；
- 2.给定一个函数，执行对方案数最后一位的提取；
T 最最最核心的一个操作一定是如何计算方案数（在容量为V，种类为N的情况下），这里和第一题：P1164 小A点菜的做法是一样的；
T 我们定义 \(dp_v\) 为装满容量为v的背包的方案数，开始时，dp[0] = 1;
T dp方程： \(dp_v = dp_v + dp_{v-w_i}\) ;
T 那么接下来，如何让一个物品作废呢，很简单，我们在计算状态转移方程之前特判即可；
T 然后是，如何提取方案数；
T 相信这个没人不会吧，直接模10即可；
E 我们开始编写；
M 编译失败：原因是：memset我没include；
E 修改；
M TLE，目前拿了80分，我想想怎么优化一下；
T 我们注意到（ 注意力惊人 ）：dp[j]的含义就是背包容量为j时的方案数，而这里的dp数组实际上包含了j从1至m的全部解，
也就是说，我们没必要在main中控制背包容量，直接在solve时指定背包容量为最大，这样仅需一次计算就得到了这一行的解；
T 真是 机智如我 ；
E 修改
M 两个点WA，五个点TLE，仍然80pts；
T 看来近似 \(O(n^2 \times m)\) 的算法不可行，我们只能尝试降低时间复杂度；
T 思考了1h，没什么思路，看看题解
T 题解真是“藏龙卧虎”，讲得好像对，又好像不对的，经过我的甄选，从五篇中总结出来了思路；
T 这里引入一个定理：往背包中放东西的最优解与顺序无关；
T 这是显然的，难道题目换一换物品的顺序最优解就不一样了？
T 所以，我们可以大胆假设最后一个物品正好是我们不能选的那个i，而不选i的方案数就等于总方案数减去选i的方案数；
T 所以我们定义 \(g_j\) 表示容量为j不选i的方案数；
T 那么 \(g_0\) 显然为1；
T 我们有： g[j] = (f[j] - g[j - w]）
T 那么对于j |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
