信息學(xué)奧賽NOIP普及組歷屆試題分析

1、NOIP普及組歷屆試題分析NOIP普及組題型分布普及組題型分布題型題型題目題目枚舉枚舉掃雷游戲掃雷游戲(2015p2)(2015p2)、珠心算測驗、珠心算測驗(2014p1)(2014p1)數(shù)字統(tǒng)計數(shù)字統(tǒng)計(2010p1)(2010p1)、比例簡化、比例簡化(2014p2)(2014p2)模擬模擬金幣金幣(2015p1)(2015p1)、螺旋方陣螺旋方陣(2014p3)(2014p3)、計數(shù)問題、計數(shù)問題(2013p1)(2013p1)、字符串字符串?dāng)?shù)字反轉(zhuǎn)數(shù)字反轉(zhuǎn)(2011p1)(2011p1)、統(tǒng)計單詞個數(shù)、統(tǒng)計單詞個數(shù)(2011p2)(2011p2)貪心貪心NOIP普及組題型分布普及組題

2、型分布題型題型題目題目簡單簡單動態(tài)規(guī)劃動態(tài)規(guī)劃子矩陣子矩陣(2014p4)(2014p4)、小朋友的數(shù)字、小朋友的數(shù)字(2013p3)(2013p3)數(shù)學(xué)數(shù)學(xué)/ /數(shù)論數(shù)論數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)表達式求值表達式求值(2013p2)(2013p2)、圖論圖論（提高組）（提高組）車站分級車站分級(2013p4 (2013p4 拓?fù)渑判蛲負(fù)渑判? )一、枚舉類試題一、枚舉類試題n枚舉法的基本思想是根據(jù)提出的問題枚舉所枚舉法的基本思想是根據(jù)提出的問題枚舉所有可能的解，并用問題給定的條件檢驗?zāi)男┯锌赡艿慕?，并用問題給定的條件檢驗?zāi)男┙馐切枰?，哪些解是不需要的。能使條件解是需要的，哪些解是不需要的。能使條件成

3、立，即為其解。成立，即為其解。n枚舉法其實是最簡單的搜索算法。枚舉法其實是最簡單的搜索算法。珠心算測驗珠心算測驗 (noip2014普及組第一題普及組第一題)n珠心算是一種通過在腦中模擬算盤變化來完成快珠心算是一種通過在腦中模擬算盤變化來完成快速運算的一種計算技術(shù)。珠心算訓(xùn)練，既能夠開速運算的一種計算技術(shù)。珠心算訓(xùn)練，既能夠開發(fā)智力，又能夠為日常生活帶來很多便利，因而發(fā)智力，又能夠為日常生活帶來很多便利，因而在很多學(xué)校得到普及。在很多學(xué)校得到普及。 n某學(xué)校的珠心算老師采用一種快速考察珠心算加某學(xué)校的珠心算老師采用一種快速考察珠心算加法能力的測驗方法。他隨機生成一個正整數(shù)集合，法能力的測驗方法

4、。他隨機生成一個正整數(shù)集合，集合中的數(shù)各不相同，然后要求學(xué)生回答：其中集合中的數(shù)各不相同，然后要求學(xué)生回答：其中有多少個數(shù)，恰好等于集合中另外兩個（不同的）有多少個數(shù)，恰好等于集合中另外兩個（不同的）數(shù)之和？數(shù)之和？ 最近老師出了一些測驗題，請你幫忙最近老師出了一些測驗題，請你幫忙求出答案。求出答案。 珠心算測驗珠心算測驗 (noip2014普及組第一題普及組第一題)n【輸入輸入】 輸入共兩行，第一行包含一個整數(shù)輸入共兩行，第一行包含一個整數(shù)n，表示測試，表示測試題中給出的正整數(shù)個數(shù)。題中給出的正整數(shù)個數(shù)。 第二行有第二行有n個正整數(shù)，每兩個正整數(shù)之間用一個個正整數(shù)，每兩個正整數(shù)之間用一個空格

5、隔開，表示測試題中給出的正整數(shù)?？崭窀糸_，表示測試題中給出的正整數(shù)。 n【輸出輸出】 輸出共一行，包含一個整數(shù)，表示測驗題答案。輸出共一行，包含一個整數(shù)，表示測驗題答案。n【樣例輸入樣例輸入】【樣例輸出樣例輸出】 4 2 1 2 3 4對于對于100%的數(shù)據(jù)，的數(shù)據(jù)，3 n 100測驗題給出的正整數(shù)大小不超過測驗題給出的正整數(shù)大小不超過10,000。 試題分析試題分析n題意大意：給你題意大意：給你n個數(shù)，在這個數(shù)，在這n個數(shù)中，找個數(shù)中，找到滿足到滿足A+B=C的個數(shù)，的個數(shù)，注意不是這個等式注意不是這個等式的個數(shù)的個數(shù)。n樣例中，樣例中，1,2,3,4有有1+2=3，1+3=4兩個。兩個。n

6、由于本題數(shù)據(jù)規(guī)模由于本題數(shù)據(jù)規(guī)模n=100，我們可以直接，我們可以直接枚舉枚舉C, A, B，三層循環(huán)解決問題。，三層循環(huán)解決問題。數(shù)字統(tǒng)計數(shù)字統(tǒng)計 (noip2010普及組第一題普及組第一題) 請統(tǒng)計某個給定范圍請統(tǒng)計某個給定范圍L, R的所有整數(shù)中，數(shù)字的所有整數(shù)中，數(shù)字2出現(xiàn)出現(xiàn)的次數(shù)。的次數(shù)。 比如在給定范圍比如在給定范圍2, 22，數(shù)字，數(shù)字2在數(shù)在數(shù)2中出現(xiàn)了中出現(xiàn)了1次，在次，在數(shù)數(shù)12中出現(xiàn)了中出現(xiàn)了1次，在數(shù)次，在數(shù)20中出現(xiàn)了中出現(xiàn)了1次，在數(shù)次，在數(shù)21中出中出現(xiàn)了現(xiàn)了1次，在數(shù)次，在數(shù)22中出現(xiàn)了中出現(xiàn)了2次，所以數(shù)字次，所以數(shù)字2在該范圍內(nèi)在該范圍內(nèi)一共出現(xiàn)了一共出現(xiàn)

7、了6次。次。n輸入格式輸入格式 輸入共一行，為兩個正整數(shù)輸入共一行，為兩個正整數(shù)L和和R，之間用一個空格隔，之間用一個空格隔開。開。n輸出格式輸出格式 輸出共輸出共1行，表示數(shù)字行，表示數(shù)字2出現(xiàn)的次數(shù)。出現(xiàn)的次數(shù)。n樣例輸入：樣例輸入：2 22n樣例輸出：樣例輸出：6掃雷游戲掃雷游戲 (noip2015普及組第二題普及組第二題) 掃雷游戲是一款十分經(jīng)典的單機小游戲。掃雷游戲是一款十分經(jīng)典的單機小游戲。 在在 n 行行 m 列的雷區(qū)中有一些格子含有地雷列的雷區(qū)中有一些格子含有地雷（稱之為地雷格）（稱之為地雷格） ，其他格子不含地雷（稱之，其他格子不含地雷（稱之為非地雷格）為非地雷格） 。玩家翻

8、開一個非地雷格時，該。玩家翻開一個非地雷格時，該格將會出現(xiàn)一個數(shù)字格將會出現(xiàn)一個數(shù)字提示周圍格子中有多提示周圍格子中有多少個是地雷格。少個是地雷格。 游戲的目標(biāo)是在不翻出任何地游戲的目標(biāo)是在不翻出任何地雷格的條件下，找出所有的非地雷格。雷格的條件下，找出所有的非地雷格。 現(xiàn)在給出現(xiàn)在給出n行行m列的雷區(qū)中的地雷分布，列的雷區(qū)中的地雷分布， 要要求計算出每個非地雷格周圍的地雷格數(shù)。求計算出每個非地雷格周圍的地雷格數(shù)。注：一個格子的周圍格子包括其上、下、左、注：一個格子的周圍格子包括其上、下、左、右、左上、右上、左下、右下八個方向上與之右、左上、右上、左下、右下八個方向上與之直接相鄰的格子。直接相

9、鄰的格子。 掃雷游戲掃雷游戲 (noip2015普及組第二題普及組第二題) 輸入樣例輸入樣例 13 3*?*? 輸入樣例輸入樣例 22 3?*?*? 輸出樣例輸出樣例 1mine.out*102211*1 輸出樣例輸出樣例 2mine.out2*1*21 對于對于 100%的數(shù)據(jù)，的數(shù)據(jù)，1n100，1m100 比例簡化比例簡化 (noip2014普及組第二題普及組第二題)n在社交媒體上，經(jīng)常會看到針對某一個觀點同意與在社交媒體上，經(jīng)常會看到針對某一個觀點同意與否的民意調(diào)查以及結(jié)果。例如，對某否的民意調(diào)查以及結(jié)果。例如，對某 一觀點表示一觀點表示支持的有支持的有 1498 人，反對的有人，反對

10、的有 902 人，那么贊同與人，那么贊同與反對的比例可以簡單的記為反對的比例可以簡單的記為1498:902。n不過，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來，大不過，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來，大多數(shù)人肯定不會滿意。因為這個比例的數(shù)值太大，多數(shù)人肯定不會滿意。因為這個比例的數(shù)值太大，難以一眼看出它們的關(guān)系。對于上面這個例子，如難以一眼看出它們的關(guān)系。對于上面這個例子，如果把比例記為果把比例記為 5:3，雖然與，雖然與 真實結(jié)果有一定的誤差，真實結(jié)果有一定的誤差，但依然能夠較為準(zhǔn)確地反映調(diào)查結(jié)果，同時也顯得但依然能夠較為準(zhǔn)確地反映調(diào)查結(jié)果，同時也顯得比較直觀。比較直觀。n現(xiàn)給出支持人數(shù)現(xiàn)給出支

11、持人數(shù) A，反對人數(shù)，反對人數(shù) B，以及一個上限，以及一個上限 L，請你將請你將 A 比比 B 化簡為化簡為 A比比 B，要求在，要求在 A和和 B均均不大于不大于 L 且且 A和和 B互質(zhì)（兩個整數(shù)的最大公約數(shù)互質(zhì)（兩個整數(shù)的最大公約數(shù)是是 1）的前提下，）的前提下，A/B A/B 且且 A/B - A/B 的值的值盡可能小。盡可能小。 比例簡化比例簡化 (noip2014普及組第二題普及組第二題)n輸入格式輸入格式n輸入共一行，包含三個整數(shù)輸入共一行，包含三個整數(shù) A，B，L，每兩個整，每兩個整數(shù)之間用一個空格隔開，分別表示支持人數(shù)、反對數(shù)之間用一個空格隔開，分別表示支持人數(shù)、反對人數(shù)以及

12、上限。人數(shù)以及上限。n輸出格式輸出格式n輸出共一行，包含兩個整數(shù)輸出共一行，包含兩個整數(shù) A，B，中間用一個，中間用一個空格隔開，表示化簡后的比例?？崭窀糸_，表示化簡后的比例。n樣例輸入樣例輸入n1498 902 10n樣例輸出樣例輸出n5 3二、模擬類試題二、模擬類試題n有些問題，我們很難建立數(shù)學(xué)模型，或者很難有些問題，我們很難建立數(shù)學(xué)模型，或者很難用計算機建立遞推、遞歸、枚舉、回溯法等算用計算機建立遞推、遞歸、枚舉、回溯法等算法。在這種情況下，一般采用模擬策略。法。在這種情況下，一般采用模擬策略。n所謂模擬策略就是模擬某個過程，通過改變數(shù)所謂模擬策略就是模擬某個過程，通過改變數(shù)學(xué)模型的各種

13、參數(shù)，進而觀察變更這些參數(shù)所學(xué)模型的各種參數(shù)，進而觀察變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計。引起過程狀態(tài)的變化，由此展開算法設(shè)計。 金幣金幣 (noip2015普及組第一題普及組第一題)n國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（第二天和第三天），每天收到兩枚金幣；之后三天幣；之后兩天（第二天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、十天），每天收到四枚金幣十天），每天收

14、到四枚金幣；這種工資發(fā)放模式會一直這樣延續(xù)；這種工資發(fā)放模式會一直這樣延續(xù)下去：當(dāng)連續(xù)下去：當(dāng)連續(xù)N天每天收到天每天收到N枚金幣后，騎士會在之后的連續(xù)枚金幣后，騎士會在之后的連續(xù)N+1天天里，每天收到里，每天收到N+1枚金幣。枚金幣。請計算在前請計算在前K天里，騎士一共獲得了多少金幣。天里，騎士一共獲得了多少金幣。n 輸入格式：輸入格式：輸入文件只有輸入文件只有1行，包含一個正整數(shù)行，包含一個正整數(shù)K，表示發(fā)放金幣的天數(shù)。，表示發(fā)放金幣的天數(shù)。n輸出格式：輸出格式：輸出文件只有輸出文件只有1行，包含一個正整數(shù)，即騎士收到的金幣數(shù)。行，包含一個正整數(shù)，即騎士收到的金幣數(shù)。n輸入輸出樣例輸入輸出樣

15、例 n輸入樣例：輸入樣例： 1000n輸出樣例：輸出樣例：29820螺旋方陣螺旋方陣 (noip2014普及組第三題普及組第三題)n一個一個n行行n列的螺旋矩陣可由如下方法生成：列的螺旋矩陣可由如下方法生成：n 從矩陣的左上角從矩陣的左上角(第第1行第行第1列列)出發(fā)，初始時向右出發(fā)，初始時向右移動；如果前方是未曾經(jīng)過的格子，則繼續(xù)前進，移動；如果前方是未曾經(jīng)過的格子，則繼續(xù)前進，否則右轉(zhuǎn)；重復(fù)上述操作直至經(jīng)過矩陣中所有格子。否則右轉(zhuǎn)；重復(fù)上述操作直至經(jīng)過矩陣中所有格子。根據(jù)經(jīng)過順序，在格子中依次填入根據(jù)經(jīng)過順序，在格子中依次填入1,2,3,.，便構(gòu)，便構(gòu)成了一個螺旋矩陣。成了一個螺旋矩陣。n

16、 現(xiàn)給出矩陣大小現(xiàn)給出矩陣大小n以及以及i和和j，請你求出該矩陣中第，請你求出該矩陣中第i行第行第j列的數(shù)是多少。列的數(shù)是多少。n 下圖是一個下圖是一個n=4時的螺旋矩陣。時的螺旋矩陣。螺旋方陣螺旋方陣 (noip2014普及組第三題普及組第三題)n輸入格式輸入格式n輸入共一行，包含三個整數(shù)輸入共一行，包含三個整數(shù) n，i，j，每兩個整數(shù)，每兩個整數(shù)之間用一個空格隔開，分別表示矩陣大小、待求的之間用一個空格隔開，分別表示矩陣大小、待求的數(shù)所在的行號和列號。數(shù)所在的行號和列號。n輸出格式輸出格式n輸出共一行，包含一個整數(shù)，表示相應(yīng)矩陣中第輸出共一行，包含一個整數(shù)，表示相應(yīng)矩陣中第 i 行第行第

17、j 列的數(shù)。列的數(shù)。n樣例輸入：樣例輸入：4 2 3n 樣例輸出：樣例輸出：14n對于對于 50%的數(shù)據(jù)，的數(shù)據(jù)，1 n 100;對于對于 100%的數(shù)據(jù)，的數(shù)據(jù)，1 n 30,000，1 i n，1 j n。 螺旋方陣試題分析螺旋方陣試題分析n本題首先讓我們想到傳統(tǒng)的模擬，從本題首先讓我們想到傳統(tǒng)的模擬，從1,1開開始往數(shù)組中填充數(shù)字，但對于始往數(shù)組中填充數(shù)字，但對于30000,30000的數(shù)組，直接爆零。的數(shù)組，直接爆零。n對于讀入的對于讀入的n, x, y，先判斷，先判斷(x,y)在第幾圈，在第幾圈，再模擬圈內(nèi)的數(shù)字。再模擬圈內(nèi)的數(shù)字。螺旋方陣試題分析螺旋方陣試題分析n如：如：n=4,

18、(2,2)在第在第2圈，圈，(3,1)在第在第1圈。圈。nn=6，(4,5)在第在第2圈圈螺旋方陣試題分析螺旋方陣試題分析n目標(biāo)位置目標(biāo)位置(i,j)到底在當(dāng)前這一圈的第幾個位置？到底在當(dāng)前這一圈的第幾個位置？n如目標(biāo)數(shù)如目標(biāo)數(shù)26所在的位置所在的位置(4,5)，在第，在第2圈的什么圈的什么位置？位置？n分兩種情況：分兩種情況：n1）目標(biāo)數(shù)）目標(biāo)數(shù)(i,j)在上行或右行；在上行或右行；n i+j-2q+1n2）目標(biāo)數(shù)）目標(biāo)數(shù)(i,j)在下行或左行；在下行或左行；n 距離第一個數(shù)的距離距離第一個數(shù)的距離n i+j-2q+1計數(shù)問題計數(shù)問題 (noip2013普及組第一題普及組第一題)n試計算在區(qū)

19、間試計算在區(qū)間1到到n的所有整數(shù)中，數(shù)字的所有整數(shù)中，數(shù)字x（0 x9）共出現(xiàn)了多少次？共出現(xiàn)了多少次？例如，在例如，在1到到11中，即在中，即在1、2、3、4、5、6、7、8、9、10、11中，數(shù)字中，數(shù)字1出現(xiàn)了出現(xiàn)了4次。次。n輸入：輸入： 輸入共輸入共1行，包含行，包含2個整數(shù)個整數(shù)n、x，之間用一個空格隔，之間用一個空格隔開。開。 輸出：輸出： 輸出共輸出共1行，包含一個整數(shù)，表示行，包含一個整數(shù)，表示x出現(xiàn)的次數(shù)。出現(xiàn)的次數(shù)。 n輸入示例：輸入示例： 11 1n輸出示例：輸出示例： 4n其他說明：其他說明： 對于對于100%的數(shù)據(jù)，的數(shù)據(jù)，1n1,000,000，0 x9。 三、字

20、符串類試題三、字符串類試題n對于字符串、表達式的求解、對于字符串、表達式的求解、 大整數(shù)的處理大整數(shù)的處理等等，我們經(jīng)常采用字符串來處理。等等，我們經(jīng)常采用字符串來處理。n字符串處理常見函數(shù)：字符串處理常見函數(shù)：數(shù)字反轉(zhuǎn)數(shù)字反轉(zhuǎn) (noip2011普及組第一題普及組第一題)n給定一個整數(shù)，請將該數(shù)各個位上數(shù)字反轉(zhuǎn)得到一個新給定一個整數(shù)，請將該數(shù)各個位上數(shù)字反轉(zhuǎn)得到一個新數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見形式，即除非給定的原數(shù)數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零（如：輸入（如：輸入-380，輸出，輸出

21、-83）。）。n輸入輸入 輸入共輸入共1行，一個整數(shù)行，一個整數(shù)N。n輸出輸出 輸出共輸出共1行，一個整數(shù)，表示反轉(zhuǎn)后的新數(shù)。行，一個整數(shù)，表示反轉(zhuǎn)后的新數(shù)。n樣例輸入樣例輸入 123n樣例輸出樣例輸出 321統(tǒng)計單詞個數(shù)統(tǒng)計單詞個數(shù) (noip2011普及組第二題普及組第二題)n一般的文本編輯器都有查找單詞的功能，該功一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計出特定單詞在文章中出現(xiàn)的次數(shù)。的還能統(tǒng)計出特定單詞在文章中出現(xiàn)的次數(shù)。現(xiàn)在，請你編程實現(xiàn)這一功能，具體要求現(xiàn)在，請你編程實現(xiàn)這一功能，具體要求是：給

22、定一個單詞，請你輸出它在給定的文章是：給定一個單詞，請你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時，不區(qū)分大小寫，但要求完全匹配，配單詞時，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨立單詞在不即給定單詞必須與文章中的某一獨立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例區(qū)分大小寫的情況下完全相同（參見樣例1），），如果給定單詞僅是文章中某一單詞的一部分則如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例不算匹配（參見樣例2）。）。 統(tǒng)計單詞個數(shù)統(tǒng)計單詞個數(shù) (noip2011普及組第二題普及組第二題)n輸入

23、格式輸入格式n第第1行為一個字符串，其中只含字母，表示給定單詞；行為一個字符串，其中只含字母，表示給定單詞；第第2行為一個字符串，其中只可能包含字母和空格，行為一個字符串，其中只可能包含字母和空格，表示給定的文章。表示給定的文章。n輸出格式輸出格式n只有一行，如果在文章中找到給定單詞則輸出兩個整只有一行，如果在文章中找到給定單詞則輸出兩個整數(shù)，兩個整數(shù)之間用一個空格隔開，分別是單詞在文數(shù)，兩個整數(shù)之間用一個空格隔開，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時，單詞首字母在文章中的位置，位置從一次出現(xiàn)時，單詞首字母在文章中

24、的位置，位置從0開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一個整數(shù)個整數(shù)-1。統(tǒng)計單詞個數(shù)統(tǒng)計單詞個數(shù) (noip2011普及組第二題普及組第二題)n樣例輸入樣例輸入1： To to be or not to be is a questionn樣例輸出樣例輸出1：2 0n樣例輸入樣例輸入2：to Did the Ottoman Empire lose its power at that time n樣例輸出樣例輸出2：-1【輸入輸出樣例輸入輸出樣例2說明說明】表示給定的單詞表示給定的單詞to在文章中沒有出現(xiàn)，輸出整數(shù)在文章中沒有出現(xiàn)，輸出整數(shù)-1

25、。n注釋說明注釋說明 1單詞長度單詞長度10。1文章長度文章長度1,000,000。六、簡單動態(tài)規(guī)劃類試題六、簡單動態(tài)規(guī)劃類試題n動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種思想方動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種思想方法。一般我們從初始法。一般我們從初始階段階段出發(fā)，枚舉每個階段的所有出發(fā)，枚舉每個階段的所有狀態(tài)狀態(tài)，在狀態(tài)轉(zhuǎn)移的過程中，我們需要，在狀態(tài)轉(zhuǎn)移的過程中，我們需要決策決策。根據(jù)每。根據(jù)每一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終在變化的狀態(tài)中產(chǎn)生一個決策序列。動態(tài)規(guī)劃就是為在變化的狀態(tài)中產(chǎn)生一個決策序列。動態(tài)規(guī)劃就是為了使產(chǎn)生的

26、決策序列在符合某種條件下達到最優(yōu)。了使產(chǎn)生的決策序列在符合某種條件下達到最優(yōu)。n普及組一般考查的動態(tài)規(guī)劃：普及組一般考查的動態(tài)規(guī)劃：01背包，最長上升子序背包，最長上升子序列，一些簡單的線性動規(guī)。列，一些簡單的線性動規(guī)。采藥采藥 （noip2005普及組第三題）普及組第三題）n辰辰是個天資聰穎的孩子，他的夢想是成為世辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草出了一個難題。醫(yī)師把他帶到一個到處都是草藥

27、的山洞里對他說：藥的山洞里對他說：“孩子，這個山洞里有一孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應(yīng)該可以讓采到的草藥是一個聰明的孩子，你應(yīng)該可以讓采到的草藥的總價值最大。的總價值最大?！?采藥采藥 （noip2005普及組第三題）普及組第三題）n輸入格式：輸入格式：第一行有兩個整數(shù)第一行有兩個整數(shù)T和和M，T代表總共能夠用來采藥的時間，代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在行每行包括兩個在1到