Table of Contents

1. 1. 題目描述
   2. 思考
2. 1. 題目描述
   2. 思考

題目：洛谷P1048 [NOIP 2005 普及組]采藥
難度：普及-

題目描述

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應(yīng)該可以讓采到的草藥的總價值最大。”

如果你是辰辰，你能完成這個任務(wù)嗎？

輸入格式

第一行有 2 個整數(shù) T（1≤T≤1000）和 M（1≤M≤100），用一個空格隔開，T 代表總共能夠用來采藥的時間，M 代表山洞里的草藥的數(shù)目。

接下來的 M 行每行包括兩個在 1 到 100 之間（包括 1 和 100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。

輸出格式

輸出在規(guī)定的時間內(nèi)可以采到的草藥的最大總價值。

思考

R 我們簡化一下題目：有n種草藥，每種都有其價值和時間，總時間為T，求出最大能取得的價值

T 標(biāo)準(zhǔn)的01背包問題+套殼版

T 仍然是按照01背包的方式去敲，這里的時間即為重量，T為總重量；

T 我們再寫一遍dp方程，加深一下印象： $ dp_i,j = Max(dp_i-1,j,dp_i-1,j-wi+v_i) $

E 編寫完成

M 但是，WA了，樣例倒是沒問題，不知道為什么，我們準(zhǔn)備打印dp數(shù)組；

E 我們找到了問題：當(dāng) $ j<w_i $ 時數(shù)組會越界，我們需要特判，

這時的方程為 $ dp_i,j = dp_i-1,j $ ;

E AC;

T WC，我竟然做了一個NOIP(眾所周知，NOIP俗稱NOI PLUS)（bushi）；

題目：洛谷P1802 5倍經(jīng)驗日
難度：普及-

題目描述

題目背景

現(xiàn)在樂斗有活動了！每打一個人可以獲得 5 倍經(jīng)驗！absi2011 卻無奈的看著那一些比他等級高的好友，想著能否把他們干掉。干掉能拿不少經(jīng)驗的。

題目描述

現(xiàn)在 absi2011 拿出了 \(x\) 個迷你裝藥物（嗑藥打人可恥…），準(zhǔn)備開始與那些人打了。

由于迷你裝藥物每個只能用一次，所以 absi2011 要謹(jǐn)慎的使用這些藥。悲劇的是，用藥量沒達(dá)到最少打敗該人所需的屬性藥藥量，則打這個人必輸。例如他用 \(2\) 個藥去打別人，別人卻表明 \(3\) 個藥才能打過，那么相當(dāng)于你輸了并且這兩個屬性藥浪費了。

現(xiàn)在有 \(n\) 個好友，給定失敗時可獲得的經(jīng)驗、勝利時可獲得的經(jīng)驗，打敗他至少需要的藥量。

要求求出最大經(jīng)驗 \(s\)，輸出 \(5s\)。

輸入格式

第一行兩個數(shù)，\(n\) 和 \(x\)。

后面 \(n\) 行每行三個數(shù)，分別表示失敗時獲得的經(jīng)驗 \(\mathit{lose}_i\)，勝利時獲得的經(jīng)驗 \(\mathit{win}_i\) 和打過要至少使用的藥數(shù)量 \(\mathit{use}_i\)。

輸出格式

一個整數(shù)，最多獲得的經(jīng)驗的五倍。

思考

R 我們?nèi)匀缓喕幌骂}目：有n個物品，每個物品有一個重量 \(w_i\) 和兩個價值 \(va_i,vb_i\)
其中， \(va_i < vb_i\) ,我們一共能拿重量為 \(x\) 的物品，我們需要輸出最大的總價值，特別的， \(va_i\) 是不需要增加重量就能得到的價值，而想獲得 \(vb_i\) 需要使自己增加 \(w_i\) 的重量
T 那么，顯然的，這還是01背包問題（因為本質(zhì)還是每種物品只能取、不取）
T 我們?nèi)匀话凑誨p的套路分析：

• dp數(shù)組定義： \(dp_{i,j}\) 為在容量為v的包中任選物品[0-i]能取得的最大價值
• 狀態(tài)劃分：拿、不拿
• 貢獻(xiàn)、轉(zhuǎn)移：
  若不拿：價值為 \(dp_{i-1,j}+va_i\)
  若拿：價值為 \(dp_{i-1,j-w_i}+vb_i\)
• 初始化：
  \(dp_0v\) :這里代表選0號物品的最大價值，顯然都為 \(va_0\) ;
  \(dp_i0\) :這里為任選物品在背包空間為0時的價值，顯然都為 \(va_i\) ;
• dp方程： \(dp_{i,j} = Max(dp_{i-1,j}+va_i,dp_{i-1,j-w_i}+vb_i)\) ;

E 我們開始編寫；
M 那么，不對，重新寫，我們按照AI的方式進(jìn)行重新設(shè)計
E 我們修改定義 \(dp_{i,j}\) 為在容量為j的包中選到i件物品能取得的最大價值
E 我們重構(gòu)一下；
E 一個點WA了
T 讓我們一起說一句名言：十年OI一場空，不開long long見祖宗
T 當(dāng)然，十年OI一場空，開了long long也見祖宗（如果哪個好人出了O(n²)的算法，n還>=64，那就自求多福吧）；