Table of Contents

1. 概述：
2. 第一題：P1164 小A點(diǎn)菜
   1. 題目：
   2. 解題過(guò)程：
3. 第二題：P2871 [USACO07DEC] Charm Bracelet S
   1. 題目：
   2. 解題過(guò)程：
4. 第三題：P2925 [USACO08DEC] Hay For Sale S
   1. 題目描述
   2. 解題過(guò)程：
5. 第四題：P4141 消失之物 （難度：提高-）
   1. 題目描述：
   2. 解題過(guò)程：
6. 今日總結(jié)：

P.S.:挑戰(zhàn)3個(gè)月達(dá)省一的第12天，目前階段：還是TMD 動(dòng)態(tài)規(guī)劃之背包問(wèn)題；
歡迎收看今天的爆0日志：

概述：

完成了4題
寫(xiě)了一篇題解
修理了一下我的kali linux和主系統(tǒng)的emacs

第一題：P1164 小A點(diǎn)菜

題目：

uim 神犇拿到了 uoi 的 ra（鐳牌）后，立刻拉著基友小 A 到了一家……餐館，很低端的那種。

uim 指著墻上的價(jià)目表（太低級(jí)了沒(méi)有菜單），說(shuō)：“隨便點(diǎn)”。

## 題目描述

不過(guò) uim 由于買(mǎi)了一些書(shū)，口袋里只剩 \(M\) 元 \((0 < M \le 10000)\)。

餐館雖低端，但是菜品種類(lèi)不少，有 \(N\) 種 \((1 \le N \le 100)\)，第 \(i\) 種賣(mài) \(a_i\) 元 \((0 < a_i \le 1000)\)。由于是很低端的餐館，所以每種菜只有一份。

小 A 奉行“不把錢(qián)吃光不罷休”的原則，所以他點(diǎn)單一定剛好把 uim 身上所有錢(qián)花完。他想知道有多少種點(diǎn)菜方法。

由于小 A 肚子太餓，所以最多只能等待 \(1\) 秒。

## 輸入格式

第一行兩個(gè)整數(shù) \(N\) 和 \(M\)，分別表示菜品種類(lèi)和 uim 身上的錢(qián)數(shù)。

第二行 \(N\) 個(gè)正整數(shù) \(a_i\)（可能有重復(fù)），用空格隔開(kāi)，分別表示每種菜的價(jià)格。

## 輸出格式

一個(gè)正整數(shù)，表示點(diǎn)菜方案數(shù)，保證答案的范圍在 \([0,2^{31}-1]\) 之內(nèi)（不超過(guò) C/C++的 int 范圍）。

## 說(shuō)明/提示

2020.8.29，增添一組 hack 數(shù)據(jù) by @yummy

解題過(guò)程：

R 這道題跟我們之前做的所有背包問(wèn)題都不太一樣，這次是計(jì)數(shù)背包；
T 我們需要重新設(shè)計(jì)dp數(shù)組和狀態(tài)轉(zhuǎn)移方程；
T 對(duì)于dp數(shù)組的定義： \(dp_v\) 代表正好花完v元的方案數(shù)；
T 狀態(tài)劃分：買(mǎi)i、不買(mǎi)i；
T 轉(zhuǎn)移方程： \(dp_v = dp_v + dp_{v-w_i}\) ;
T 解釋一下： \(dp_v\) 由不買(mǎi)（即 \(dp_v\) ）和買(mǎi)（即 \(dp_{v-w_i}\) ）轉(zhuǎn)移來(lái)，
更具體的說(shuō)，不買(mǎi)時(shí)，方案數(shù)和到 \(i-1\) 為止的方案數(shù)一致，若買(mǎi)，方案數(shù)和 到 \(i-1\) 為止時(shí)背包容量為 \(v-w_i\) 時(shí)一致（因?yàn)橐粘鑫锲穒的重量）；
T 初始化： i為0時(shí)（我們的物品編號(hào)為1-n），相當(dāng)于沒(méi)有任何物品，此時(shí)的方案數(shù) \(dp_0 = 1\) （注意，僅容量為0時(shí)值為1，其余情況均不可能填滿，為0）;
E 至此，分析完成，我們開(kāi)始編寫(xiě);
E 那么，最終用時(shí)21min，AC；
T 話說(shuō)回來(lái)，他說(shuō)的Hack數(shù)據(jù)跑哪去了？？？

第二題：P2871 [USACO07DEC] Charm Bracelet S

題目：

有 \(N\) 件物品和一個(gè)容量為 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，價(jià)值是 \(D_i\)。求解將哪些物品裝入背包可使這些物品的重量總和不超過(guò)背包容量，且價(jià)值總和最大。

## 輸入格式
第一行：物品個(gè)數(shù) \(N\) 和背包大小 \(M\)。
第二行至第 \(N+1\) 行：第 \(i\) 個(gè)物品的重量 \(W_i\) 和價(jià)值 \(D_i\)。

## 輸出格式

輸出一行最大價(jià)值

## 說(shuō)明/提示

\(1 \le N \le 3402\)，\(1 \le M \le 12880\)，\(1 \le W_i \le 400\)，\(1 \le D \le 100\)。

解題過(guò)程：

R 好吧，又遇到水題了，不過(guò)正好練練我的速度；
T 表示一下對(duì)題目的尊重，我們?nèi)匀徽J(rèn)真的看一遍：給定物品和背包，求出最大價(jià)值，沒(méi)什么問(wèn)題
T 再看一下數(shù)據(jù)范圍：3402件物品，12880的背包（這個(gè)確實(shí)有點(diǎn)大了，不過(guò)128M的內(nèi)存限制，一維dp也沒(méi)什么問(wèn)題）；
E 我們開(kāi)始干；
E 最終用時(shí)：2min28s AC，拿捏了也是；

第三題：P2925 [USACO08DEC] Hay For Sale S

題目描述

農(nóng)民 John 面臨一個(gè)很可怕的事，因?yàn)榉婪读Χ炔淮笏运鎯?chǔ)的所有稻草都被蟑螂吃光了，他將面臨沒(méi)有稻草喂養(yǎng)奶牛的局面。在奶牛斷糧之前，John 拉著他的馬車(chē)到農(nóng)民 Don 的農(nóng)場(chǎng)中買(mǎi)一些稻草給奶牛過(guò)冬。已知 John 的馬車(chē)可以裝的下 \(C(1\le C\le5\times10^4)\) 立方的稻草。

農(nóng)民 Don 有 \(H(1\le H\le5\times10^3)\) 捆體積不同的稻草可供購(gòu)買(mǎi)，每一捆稻草有它自己的體積 \(V_i(1\le V_i\le C)\)。面對(duì)這些稻草 John 認(rèn)真的計(jì)算如何充分利用馬車(chē)的空間購(gòu)買(mǎi)盡量多的稻草給他的奶牛過(guò)冬。

現(xiàn)在給定馬車(chē)的最大容積 \(C\) 和每一捆稻草的體積 \(V_i\)，John 如何在不超過(guò)馬車(chē)最大容積的情況下買(mǎi)到最大體積的稻草？他不可以把一捆稻草分開(kāi)來(lái)買(mǎi)。

## 輸入格式

第一行兩個(gè)整數(shù)，分別為 \(C\) 和 \(H\)。
第 \(2\) 到 \(H+1\) 行:每一行一個(gè)整數(shù)代表第 \(i\) 捆稻草的體積 \(V_i\)。

## 輸出格式

一個(gè)整數(shù)，為 John 能買(mǎi)到的稻草的體積。

解題過(guò)程：

R 仍然是基本的01背包問(wèn)題，不過(guò)，少了個(gè)價(jià)值；
T 所以這就成了這道題唯一的 需要?jiǎng)狱c(diǎn)腦子的 不是很人機(jī)的地方；
T 我們只需要手動(dòng)構(gòu)造令價(jià)值與重量相等即可；
P 我們確認(rèn)一下數(shù)據(jù)范圍：物品種類(lèi)：5000，背包大小：50000；
E 開(kāi)始編寫(xiě)
T 最終用時(shí)：5min，AC

第四題：P4141 消失之物 （難度：提高-）

題目描述：

ftiasch 有 \(n\) 個(gè)物品, 體積分別是 \(w_1,w_2,\dots,w_n\)。由于她的疏忽，第 \(i\) 個(gè)物品丟失了。

“要使用剩下的 \(n-1\) 物品裝滿容積為 \(x\) 的背包，有幾種方法呢？”——這是經(jīng)典的問(wèn)題了。

她把答案記為 \(\text{cnt}(i,x)\) ，想要得到所有\(i \in [1,n]\), \(x \in [1,m]\) 的 \(\text{cnt}(i,x)\) 表格。

## 輸入格式
第一行兩個(gè)整數(shù) \(n,m\)，表示物品的數(shù)量和最大的容積。
第二行 \(n\) 個(gè)整數(shù) \(w_1,w_2,\dots,w_n\)，表示每個(gè)物品的體積。

## 輸出格式
輸出一個(gè) \(n \times m\) 的矩陣，表示 \(\text{cnt}(i,x)\) 的**末位數(shù)字**。

## 輸入輸出樣例 #1
### 輸入 #1

```
3 2
1 1 2
```

### 輸出 #1

```
11
11
21
```

## 說(shuō)明/提示
【數(shù)據(jù)范圍】
對(duì)于 \(100\%\) 的數(shù)據(jù)，\(1\le n,m \le 2000\)，且 \(1\le w_i\le 2000\)。
【樣例解釋】
如果物品 3 丟失的話，只有一種方法裝滿容量是 2 的背包，即選擇物品 1 和物品 2。
—
\(\text{upd 2023.8.11}\)：新增加五組 Hack 數(shù)據(jù)。

解題過(guò)程：

R 我們簡(jiǎn)化一下題目：給出n個(gè)物品和一個(gè)容量為m背包，但是物品和背包容量可變，具體來(lái)講，物品個(gè)數(shù)為n-1（也就是說(shuō)，其中一個(gè)不可用），背包容量為1-m，
給出每種情況下裝滿背包的方案數(shù)，輸出n*m的矩陣，其中每個(gè)元素為方案數(shù)的個(gè)位數(shù)；
T 那么具體而言，我們需要解決以下幾個(gè)子任務(wù)：

• 1.給定一個(gè)函數(shù) \(solve(x,v)\)，每次指定一個(gè)物品x不計(jì)入計(jì)算過(guò)程，返回方案數(shù)；
• 2.給定一個(gè)函數(shù)，執(zhí)行對(duì)方案數(shù)最后一位的提取；

T 最最最核心的一個(gè)操作一定是如何計(jì)算方案數(shù)（在容量為V，種類(lèi)為N的情況下），這里和第一題：P1164 小A點(diǎn)菜的做法是一樣的；
T 我們定義 \(dp_v\) 為裝滿容量為v的背包的方案數(shù)，開(kāi)始時(shí)，dp[0] = 1;
T dp方程： \(dp_v = dp_v + dp_{v-w_i}\) ;
T 那么接下來(lái)，如何讓一個(gè)物品作廢呢，很簡(jiǎn)單，我們?cè)谟?jì)算狀態(tài)轉(zhuǎn)移方程之前特判即可；
T 然后是，如何提取方案數(shù)；
T 相信這個(gè)沒(méi)人不會(huì)吧，直接模10即可；
E 我們開(kāi)始編寫(xiě)；
M 編譯失敗：原因是：memset我沒(méi)include<string.h>；
E 修改；
M TLE，目前拿了80分，我想想怎么優(yōu)化一下；
T 我們注意到（ 注意力驚人 ）：dp[j]的含義就是背包容量為j時(shí)的方案數(shù)，而這里的dp數(shù)組實(shí)際上包含了j從1至m的全部解，
也就是說(shuō)，我們沒(méi)必要在main中控制背包容量，直接在solve時(shí)指定背包容量為最大，這樣僅需一次計(jì)算就得到了這一行的解；
T 真是 機(jī)智如我 ；
E 修改
M 兩個(gè)點(diǎn)WA，五個(gè)點(diǎn)TLE，仍然80pts；
T 看來(lái)近似 \(O(n^2 \times m)\) 的算法不可行，我們只能?chē)L試降低時(shí)間復(fù)雜度；
T 思考了1h，沒(méi)什么思路，看看題解
T 題解真是“藏龍臥虎”，講得好像對(duì)，又好像不對(duì)的，經(jīng)過(guò)我的甄選，從五篇中總結(jié)出來(lái)了思路；
T 這里引入一個(gè)定理：往背包中放東西的最優(yōu)解與順序無(wú)關(guān)；
T 這是顯然的，難道題目換一換物品的順序最優(yōu)解就不一樣了？
T 所以，我們可以大膽假設(shè)最后一個(gè)物品正好是我們不能選的那個(gè)i，而不選i的方案數(shù)就等于總方案數(shù)減去選i的方案數(shù)；
T 所以我們定義 \(g_j\) 表示容量為j不選i的方案數(shù)；
T 那么 \(g_0\) 顯然為1；
T 我們有： g[j] = (f[j] - g[j - w[i]]）
T 那么對(duì)于j<w[i]時(shí)，應(yīng)該怎么辦呢；
T 注意：此時(shí)背包容量小于i的重量，意味著我們不可能放入i，所以此時(shí)dp[j]就是不含i的方案，即為g[j]；
E 那么，最終用時(shí)2小時(shí)，AC；
T 我真服了，這個(gè)題真難做，比賽遇到這個(gè)題不完蛋了嗎；
T 5min后：思考了一會(huì)，我覺(jué)得我真垃圾，我是人機(jī)；
T 等會(huì)寫(xiě)個(gè)題解吧

今日總結(jié)：

感覺(jué)還不錯(cuò)，不過(guò)寫(xiě)的題有點(diǎn)少，但是寫(xiě)了一篇題解
明天接著干吧

Upt 2025.8.22 22:14
ghostface