ACM培訓(xùn)第14-15講_動(dòng)態(tài)規(guī)劃

1、ACM程序設(shè)計(jì)第十四-十五講-動(dòng)態(tài)規(guī)劃湖南工學(xué)院 張新玉目錄目錄 什么是動(dòng)態(tài)規(guī)劃 狀態(tài) 階段 決策 一種確立狀態(tài)的方法 兩種簡(jiǎn)單的DP武器 三種特殊的動(dòng)態(tài)規(guī)劃什么是動(dòng)態(tài)規(guī)劃什么是動(dòng)態(tài)規(guī)劃 在學(xué)習(xí)動(dòng)態(tài)規(guī)劃之前你一定學(xué)在學(xué)習(xí)動(dòng)態(tài)規(guī)劃之前你一定學(xué)過(guò)搜索過(guò)搜索.那么搜索與動(dòng)態(tài)規(guī)劃有那么搜索與動(dòng)態(tài)規(guī)劃有什么關(guān)系呢什么關(guān)系呢?我們來(lái)下面的一我們來(lái)下面的一個(gè)例子個(gè)例子.數(shù)字三角形數(shù)字三角形 給你一個(gè)數(shù)字三角形給你一個(gè)數(shù)字三角形, 形式如下形式如下: 1 2 3 4 5 67 8 9 10找出從第一層到最后一層的一條找出從第一層到最后一層的一條路路,使得所經(jīng)過(guò)的權(quán)值之和最小或使得所經(jīng)過(guò)的權(quán)值之和最小或者最大者

2、最大.數(shù)字三角形數(shù)字三角形 無(wú)論對(duì)與新手還是老手，這都是再無(wú)論對(duì)與新手還是老手，這都是再熟悉不過(guò)的題了，很容易地，我們熟悉不過(guò)的題了，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程：寫出狀態(tài)轉(zhuǎn)移方程：f(i, j)=ai, j + minf(i-1, j)+f(i-1, j + 1) 對(duì)于動(dòng)態(tài)規(guī)劃算法解決這個(gè)問(wèn)題，對(duì)于動(dòng)態(tài)規(guī)劃算法解決這個(gè)問(wèn)題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫出動(dòng)態(tài)規(guī)劃的方向，比較容易地寫出動(dòng)態(tài)規(guī)劃的循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時(shí)候，也許寫出循環(huán)移非常復(fù)雜的時(shí)候，也許寫出循環(huán)式的動(dòng)態(tài)規(guī)劃就不是那么簡(jiǎn)單了。

3、式的動(dòng)態(tài)規(guī)劃就不是那么簡(jiǎn)單了。 解決方法：解決方法：記憶化搜索記憶化搜索 我們嘗試從正面的思路去分析問(wèn)題，我們嘗試從正面的思路去分析問(wèn)題，如上例，不難得出一個(gè)非常簡(jiǎn)單的遞如上例，不難得出一個(gè)非常簡(jiǎn)單的遞歸過(guò)程歸過(guò)程 : f1:=f(i-1,j+1); f2:=f(i-1,j); if f1f2 then f:=f1+ai,j else f:=f2+ai,j; 顯而易見(jiàn)，這個(gè)算法就是最簡(jiǎn)單的搜顯而易見(jiàn)，這個(gè)算法就是最簡(jiǎn)單的搜索算法。時(shí)間復(fù)雜度為索算法。時(shí)間復(fù)雜度為2n，明顯是會(huì)，明顯是會(huì)超時(shí)的。分析一下搜索的過(guò)程，實(shí)際超時(shí)的。分析一下搜索的過(guò)程，實(shí)際上，很多調(diào)用都是不必要的，也就是上，很多調(diào)用都

4、是不必要的，也就是把產(chǎn)生過(guò)的最優(yōu)狀態(tài)，又產(chǎn)生了一次。把產(chǎn)生過(guò)的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費(fèi)，很顯然，我們存放一為了避免浪費(fèi)，很顯然，我們存放一個(gè)個(gè)opt數(shù)組：數(shù)組： 記憶化搜索記憶化搜索 Opti, j - 每產(chǎn)生一個(gè)每產(chǎn)生一個(gè)f(i, j)，將，將f(i, j)的值放入的值放入opt中，以后再次調(diào)中，以后再次調(diào)用到用到f(i, j)的時(shí)候，直接從的時(shí)候，直接從opti, j來(lái)取就可以了。來(lái)取就可以了。 于是動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直于是動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來(lái)了，這樣節(jié)省了思維觀地表示出來(lái)了，這樣節(jié)省了思維的難度，減少了編程的技巧，而運(yùn)的難度，減少了編程的技巧，而運(yùn)行時(shí)

5、間只是相差常數(shù)的復(fù)雜度，而行時(shí)間只是相差常數(shù)的復(fù)雜度，而且在相當(dāng)多的情況下，遞歸算法能且在相當(dāng)多的情況下，遞歸算法能更好地避免浪費(fèi)，在比賽中是非常更好地避免浪費(fèi)，在比賽中是非常實(shí)用的實(shí)用的.記憶化的功效動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)動(dòng)態(tài)規(guī)劃的實(shí)質(zhì) 可以看出動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)就是可以看出動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)就是這也就是為什么我們常說(shuō)動(dòng)態(tài)規(guī)劃必須滿這也就是為什么我們常說(shuō)動(dòng)態(tài)規(guī)劃必須滿足重疊子問(wèn)題的原因足重疊子問(wèn)題的原因.記憶化記憶化,正符合了正符合了這個(gè)要求這個(gè)要求.狀態(tài)狀態(tài) 階段階段 決策決策 或許有一種對(duì)動(dòng)態(tài)規(guī)劃的簡(jiǎn)單或許有一種對(duì)動(dòng)態(tài)規(guī)劃的簡(jiǎn)單稱法稱法,叫分階段決策叫分階段決策.其實(shí)我認(rèn)其實(shí)我認(rèn)為這個(gè)稱法并不是很能讓人

6、理為這個(gè)稱法并不是很能讓人理解解.那么下面我們來(lái)看看階段那么下面我們來(lái)看看階段,狀態(tài)狀態(tài),決策這三者間得關(guān)系吧決策這三者間得關(guān)系吧.狀態(tài)狀態(tài) 階段階段 決策決策 狀態(tài)是表現(xiàn)出動(dòng)態(tài)規(guī)劃核心思想的一個(gè)東西狀態(tài)是表現(xiàn)出動(dòng)態(tài)規(guī)劃核心思想的一個(gè)東西.而分階段決策這個(gè)東西有似乎沒(méi)有提到狀態(tài)而分階段決策這個(gè)東西有似乎沒(méi)有提到狀態(tài),這是不科學(xué)的這是不科學(xué)的. 階段階段,有些題目并不一定表現(xiàn)出一定的階段性有些題目并不一定表現(xiàn)出一定的階段性.數(shù)字三角形的階段就是每一層數(shù)字三角形的階段就是每一層.這里我們引入這里我們引入一個(gè)概念一個(gè)概念-以前狀態(tài)以前狀態(tài).但階段不是以前狀態(tài)但階段不是以前狀態(tài),狀態(tài)是階段的表現(xiàn)形式狀

7、態(tài)是階段的表現(xiàn)形式.數(shù)字三角形的以前狀數(shù)字三角形的以前狀態(tài)就是當(dāng)前層的前一層態(tài)就是當(dāng)前層的前一層. 那什么是決策呢那什么是決策呢?我們看看下面一張圖就知道我們看看下面一張圖就知道了了.顯然,從上圖可以看出,當(dāng)前狀態(tài)通過(guò)決策,回到了以前狀態(tài).可見(jiàn)決策其實(shí)就是狀態(tài)之間的橋梁。而以前狀態(tài)也就決定了當(dāng)前狀態(tài)的情況。數(shù)字三角形的決策就是選擇相鄰的兩個(gè)以前狀態(tài)的最優(yōu)值。動(dòng)規(guī)的要訣狀態(tài)動(dòng)規(guī)的要訣狀態(tài) 我們一般在動(dòng)規(guī)的時(shí)候所用到的一我們一般在動(dòng)規(guī)的時(shí)候所用到的一些數(shù)組，也就是用來(lái)存儲(chǔ)每個(gè)狀態(tài)些數(shù)組，也就是用來(lái)存儲(chǔ)每個(gè)狀態(tài)的最優(yōu)值的。的最優(yōu)值的。 我們就從動(dòng)態(tài)規(guī)劃的要訣，也就是我們就從動(dòng)態(tài)規(guī)劃的要訣，也就是核心

8、部分核心部分“狀態(tài)狀態(tài)”開始，來(lái)逐步了解開始，來(lái)逐步了解動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃。攔截導(dǎo)彈攔截導(dǎo)彈 攔截導(dǎo)彈（攔截導(dǎo)彈（Noip2002Noip2002） 某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)系統(tǒng) 有一個(gè)缺陷：雖然它的第一發(fā)炮有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高發(fā)炮彈都不能高 于前一發(fā)的高度。于前一發(fā)的高度。 某某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以該系統(tǒng)還在試用階段，

9、所以 只有一套只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來(lái)的高度，計(jì)算這套系輸入導(dǎo)彈依次飛來(lái)的高度，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈。統(tǒng)最多能攔截多少導(dǎo)彈。攔截導(dǎo)彈攔截導(dǎo)彈 狀態(tài)的表示狀態(tài)的表示fi，表示當(dāng)?shù)?，表示?dāng)?shù)趇個(gè)導(dǎo)個(gè)導(dǎo)彈必須選擇時(shí)，前彈必須選擇時(shí)，前i個(gè)導(dǎo)彈最多能攔個(gè)導(dǎo)彈最多能攔截多少。截多少。 每個(gè)導(dǎo)彈有一定的高度，當(dāng)前狀態(tài)每個(gè)導(dǎo)彈有一定的高度，當(dāng)前狀態(tài)就是以第就是以第i個(gè)導(dǎo)彈為最后一個(gè)打的導(dǎo)個(gè)導(dǎo)彈為最后一個(gè)打的導(dǎo)彈。以前狀態(tài)就是在這個(gè)導(dǎo)彈以前彈。以前狀態(tài)就是在這個(gè)導(dǎo)彈以前打的那個(gè)導(dǎo)彈。打的那個(gè)導(dǎo)彈。 顯然這是十分能夠體現(xiàn)狀態(tài)間的聯(lián)

10、顯然這是十分能夠體現(xiàn)狀態(tài)間的聯(lián)系的題目。系的題目。最長(zhǎng)公共子串最長(zhǎng)公共子串 給出兩個(gè)字符串序列。求出這給出兩個(gè)字符串序列。求出這樣的一個(gè)最長(zhǎng)的公共子串：子樣的一個(gè)最長(zhǎng)的公共子串：子串中的每個(gè)字符都能在兩個(gè)原串中的每個(gè)字符都能在兩個(gè)原串中找到，而且每個(gè)字符的順串中找到，而且每個(gè)字符的順序和原串中的順序一致。序和原串中的順序一致。交交錯(cuò)錯(cuò)匹匹配配 交錯(cuò)匹配（最長(zhǎng)公共子串的改編）交錯(cuò)匹配（最長(zhǎng)公共子串的改編） 給你兩排數(shù)字給你兩排數(shù)字, ,只能將兩排中數(shù)字相同的兩個(gè)位置只能將兩排中數(shù)字相同的兩個(gè)位置相連相連, ,而每次相連必須有兩個(gè)匹配形成一次交錯(cuò)而每次相連必須有兩個(gè)匹配形成一次交錯(cuò), ,交交錯(cuò)的連

11、線不能再和別的交錯(cuò)連線有交點(diǎn)錯(cuò)的連線不能再和別的交錯(cuò)連線有交點(diǎn). .問(wèn)這兩排問(wèn)這兩排數(shù)字最多能形成多少個(gè)交錯(cuò)匹配數(shù)字最多能形成多少個(gè)交錯(cuò)匹配. .2 3 3 2 4 1 5 1 3 5 103 1 2 3 2 4 12 1 5 5 3 狀態(tài)的表示狀態(tài)的表示fi,jfi,j表示前表示前i i個(gè)第一排的數(shù)個(gè)第一排的數(shù)字和前字和前j j個(gè)第二排的數(shù)字搭配的最優(yōu)值。個(gè)第二排的數(shù)字搭配的最優(yōu)值。當(dāng)前的狀態(tài)就是當(dāng)前你枚舉到的一組交錯(cuò)當(dāng)前的狀態(tài)就是當(dāng)前你枚舉到的一組交錯(cuò)的后面兩個(gè)位置的后面兩個(gè)位置. .例如上圖中當(dāng)前狀態(tài)是例如上圖中當(dāng)前狀態(tài)是3 3和和1(1(第一組交錯(cuò)第一組交錯(cuò)),),枚舉他的以前狀態(tài)就有

12、枚舉他的以前狀態(tài)就有1 1 3.3.這樣在這樣在1 31 3之前會(huì)有一個(gè)最優(yōu)值存在之前會(huì)有一個(gè)最優(yōu)值存在, ,因因此可以由此得到此可以由此得到3 13 1的最優(yōu)值的最優(yōu)值. .買車票買車票 買車票買車票(Ural1031)(Ural1031) Ekaterinburg Ekaterinburg城到城到SverdlovskSverdlovsk城有城有直線形的鐵路線。直線形的鐵路線。兩城之間還有其他一些停靠站兩城之間還有其他一些?？空? ,總站總站數(shù)為數(shù)為N N。各站按照離各站按照離EkaterinburgEkaterinburg城的距離城的距離編號(hào)。編號(hào)。EkaterinburgEkaterin

13、burg城編號(hào)為城編號(hào)為1 1，SverdlovskSverdlovsk城編號(hào)為城編號(hào)為N N。買車票買車票某兩站之間車票價(jià)格由這兩站的距離某兩站之間車票價(jià)格由這兩站的距離X X決定決定. . 當(dāng)當(dāng)0X=L10X=L1時(shí)，票價(jià)為時(shí)，票價(jià)為C1C1元元. . 當(dāng)當(dāng)L1X=L2L1X=L2時(shí)，票價(jià)為時(shí)，票價(jià)為C2C2元元. . 當(dāng)當(dāng)L2X=L3L2X=L3時(shí)，票價(jià)為時(shí)，票價(jià)為C3C3元元. .當(dāng)兩站距離大于當(dāng)兩站距離大于L3L3時(shí)沒(méi)有直達(dá)票，所以有時(shí)候要買幾時(shí)沒(méi)有直達(dá)票，所以有時(shí)候要買幾次票做幾次車才行。次票做幾次車才行。比如，在上面的例圖中，比如，在上面的例圖中，2-62-6沒(méi)有直達(dá)票，有幾種買

14、沒(méi)有直達(dá)票，有幾種買票票方法可以從方法可以從2-62-6，其中一種是買，其中一種是買C2C2元的元的2-32-3車票，再買車票，再買C3C3元的元的3-63-6車票。車票。買車票買車票給定起點(diǎn)站和終點(diǎn)站還有給定起點(diǎn)站和終點(diǎn)站還有L1,L2,L3,C1,C2,C3L1,L2,L3,C1,C2,C3，求出要從，求出要從起點(diǎn)到終點(diǎn)最少要花多少錢起點(diǎn)到終點(diǎn)最少要花多少錢. .怎么怎么辦辦買車票買車票當(dāng)前所在的某個(gè)車站這一題的以前狀態(tài)其實(shí)只有這一題的以前狀態(tài)其實(shí)只有3種種.即即滿足滿足3種距離種距離(收費(fèi)收費(fèi))情況的情況的3個(gè)車站個(gè)車站.要知道這要知道這3個(gè)車站可以先做一個(gè)預(yù)個(gè)車站可以先做一個(gè)預(yù)處理處理

15、.顯然這顯然這3個(gè)車站在滿足距離限個(gè)車站在滿足距離限制的條件下應(yīng)該越遠(yuǎn)越好制的條件下應(yīng)該越遠(yuǎn)越好.買車票買車票 預(yù)處理預(yù)處理 很容易想出一個(gè)很容易想出一個(gè)N2的預(yù)處理的預(yù)處理,但是那樣但是那樣是會(huì)超時(shí)的是會(huì)超時(shí)的.由于盡量要讓車站離得遠(yuǎn)由于盡量要讓車站離得遠(yuǎn)(費(fèi)用費(fèi)用是一樣的啊是一樣的啊 )因此在每種收費(fèi)情況下因此在每種收費(fèi)情況下,每個(gè)車站的以前狀態(tài)車站一定是遞增的序列每個(gè)車站的以前狀態(tài)車站一定是遞增的序列.這里是只要這里是只要O(N)的程序的程序: for j:=1 to 3 do begin k:=en-1; for i:=en downto be do begin while (wayi

16、-wayk=be) do dec(k); pij:=k+1; end; end; 數(shù)組數(shù)組Pij表示的是表示的是I狀態(tài)的第狀態(tài)的第j種以前狀態(tài)種以前狀態(tài).買車票買車票動(dòng)態(tài)規(guī)劃的部分動(dòng)態(tài)規(guī)劃的部分for i:=be+1 to en do 枚舉當(dāng)枚舉當(dāng)前狀態(tài)前狀態(tài) begin costi:=maxlongint; for j:=1 to 3 do 枚舉枚舉以前狀態(tài)以前狀態(tài) beginif (piji) and (costi costpij + cj) then costi:=costpij+cj; end; end;動(dòng)規(guī)的要訣狀態(tài)動(dòng)規(guī)的要訣狀態(tài) 有時(shí)候當(dāng)前狀態(tài)確定后有時(shí)候當(dāng)前狀態(tài)確定后,以前狀以前

17、狀態(tài)就已經(jīng)確定態(tài)就已經(jīng)確定,則無(wú)需枚舉則無(wú)需枚舉.TomTom的煩惱的煩惱 TomTom是一個(gè)非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是一個(gè)非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車制造專業(yè)，所以畢業(yè)后他用有限的資金開是汽車制造專業(yè)，所以畢業(yè)后他用有限的資金開了一家汽車零件加工廠，了一家汽車零件加工廠， 專門為汽車制造商制專門為汽車制造商制造零件。由于資金有限，他只能先購(gòu)買一臺(tái)加工造零件。由于資金有限，他只能先購(gòu)買一臺(tái)加工機(jī)器?，F(xiàn)在他卻遇到了麻煩，多家汽車制造商需機(jī)器。現(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加要他加 工一些不同零件（由于廠家和零件不同，工一些不同零件（由于廠家和零件不同，所以給的加工費(fèi)也

18、不同），而且不同廠家對(duì)于不所以給的加工費(fèi)也不同），而且不同廠家對(duì)于不同零件的加工時(shí)間要求不同（有些加工時(shí)間要求同零件的加工時(shí)間要求不同（有些加工時(shí)間要求甚至是沖突的，但開始和結(jié)束時(shí)間相同不算沖甚至是沖突的，但開始和結(jié)束時(shí)間相同不算沖突）。突）。TomTom當(dāng)然希望能把所有的零件都加工完，當(dāng)然希望能把所有的零件都加工完，以得到更多的加工費(fèi)，但當(dāng)一些零件的加工時(shí)間以得到更多的加工費(fèi)，但當(dāng)一些零件的加工時(shí)間要求有沖突時(shí)，在某個(gè)時(shí)間內(nèi)他只能選擇某種零要求有沖突時(shí)，在某個(gè)時(shí)間內(nèi)他只能選擇某種零件加工（因?yàn)樗挥幸慌_(tái)機(jī)器），為了賺得盡量件加工（因?yàn)樗挥幸慌_(tái)機(jī)器），為了賺得盡量多的加工費(fèi)，多的加工費(fèi)，To

19、mTom不知如何進(jìn)行取舍。不知如何進(jìn)行取舍。 TomTom的煩惱的煩惱 Tom的煩惱的煩惱 按結(jié)束時(shí)間排序，枚舉結(jié)束時(shí)間作按結(jié)束時(shí)間排序，枚舉結(jié)束時(shí)間作為當(dāng)前狀態(tài)為當(dāng)前狀態(tài),以前狀態(tài)就是該結(jié)束時(shí)以前狀態(tài)就是該結(jié)束時(shí)間對(duì)應(yīng)的起始時(shí)間，這是已經(jīng)確定的間對(duì)應(yīng)的起始時(shí)間，這是已經(jīng)確定的.文字游戲文字游戲 文字游戲文字游戲(fairfox(fairfox邀請(qǐng)賽邀請(qǐng)賽1)1) 給你一份單詞表，和一個(gè)句子。求出該句子能有多少給你一份單詞表，和一個(gè)句子。求出該句子能有多少中不同的劃分方法中不同的劃分方法. .例如例如: : 單詞是單詞是ab cd a b c dab cd a b c d 句子是句子是abcd

20、abcd 他共有他共有4 4種種完全完全劃分方案劃分方案: : ab/cd a/b/c/d a/b/cd ab/c/d; ab/cd a/b/c/d a/b/cd ab/c/d; 當(dāng)前狀態(tài)就是單詞在句子中向后靠的位置當(dāng)前狀態(tài)就是單詞在句子中向后靠的位置, ,以前狀態(tài)就以前狀態(tài)就是確定這個(gè)單詞位置以后是確定這個(gè)單詞位置以后, ,除掉這個(gè)單詞長(zhǎng)度后的一除掉這個(gè)單詞長(zhǎng)度后的一個(gè)位置個(gè)位置. .狀態(tài)轉(zhuǎn)移方程是狀態(tài)轉(zhuǎn)移方程是:Fi:=Fi+Fi-:Fi:=Fi+Fi-length(wordj)length(wordj) IOI IOI中有一題中有一題前綴前綴也是類似的題目也是類似的題目. .決策中的定量

21、決策中的定量 狀態(tài)轉(zhuǎn)移方程的構(gòu)造無(wú)疑是動(dòng)態(tài)狀態(tài)轉(zhuǎn)移方程的構(gòu)造無(wú)疑是動(dòng)態(tài)規(guī)劃過(guò)程中最重要的一步規(guī)劃過(guò)程中最重要的一步,也是也是最難的一步最難的一步.對(duì)于大多數(shù)的動(dòng)態(tài)對(duì)于大多數(shù)的動(dòng)態(tài)規(guī)劃規(guī)劃,尋找狀態(tài)轉(zhuǎn)移方程有一條尋找狀態(tài)轉(zhuǎn)移方程有一條十分高效的通道十分高效的通道,就是尋找變化就是尋找變化中的不變量中的不變量.定量處理的過(guò)程也定量處理的過(guò)程也就是決策實(shí)施的過(guò)程就是決策實(shí)施的過(guò)程.尋找定量尋找定量 最佳加法表達(dá)式最佳加法表達(dá)式 有一個(gè)由有一個(gè)由1.91.9組成的數(shù)字串組成的數(shù)字串. .問(wèn)如果將問(wèn)如果將m m個(gè)加號(hào)插入到這個(gè)個(gè)加號(hào)插入到這個(gè)數(shù)字串中數(shù)字串中. .使得所形成的算術(shù)使得所形成的算術(shù)表達(dá)式的

22、值最小表達(dá)式的值最小. .或許你不明白我在說(shuō)什么,那么我們通過(guò)題目來(lái)說(shuō)明吧最佳加法表達(dá)式最佳加法表達(dá)式 這一題中的定量是什么呢這一題中的定量是什么呢?因?yàn)槭翘砣胍驗(yàn)槭翘砣爰犹?hào)加號(hào),那么添完加號(hào)后那么添完加號(hào)后,表達(dá)式的最后一表達(dá)式的最后一定是個(gè)數(shù)字串定是個(gè)數(shù)字串,這就是定量這就是定量.從這里入手從這里入手,不難發(fā)現(xiàn)可以把以前狀態(tài)認(rèn)為是在前不難發(fā)現(xiàn)可以把以前狀態(tài)認(rèn)為是在前i個(gè)字符中插入個(gè)字符中插入k-1個(gè)加號(hào)個(gè)加號(hào)(這里的這里的i是當(dāng)是當(dāng)作決策在枚舉作決策在枚舉),然后然后i+1到最后一位一到最后一位一定是整個(gè)沒(méi)有被分割的數(shù)字串定是整個(gè)沒(méi)有被分割的數(shù)字串,第第k個(gè)加個(gè)加號(hào)就添在號(hào)就添在i與與i+

23、1個(gè)數(shù)字之間個(gè)數(shù)字之間.這樣就構(gòu)這樣就構(gòu)造出了整個(gè)數(shù)字串的最優(yōu)解造出了整個(gè)數(shù)字串的最優(yōu)解.而至于前而至于前i個(gè)字符中插入個(gè)字符中插入k-1個(gè)加號(hào)個(gè)加號(hào),這又回到了這又回到了原問(wèn)題的形式原問(wèn)題的形式,也就是回到了以前狀態(tài)也就是回到了以前狀態(tài),所以狀態(tài)轉(zhuǎn)移方程就能很快的構(gòu)造出所以狀態(tài)轉(zhuǎn)移方程就能很快的構(gòu)造出來(lái)了來(lái)了.最佳加法表達(dá)式最佳加法表達(dá)式 用用fi,j,表示的是在前表示的是在前i個(gè)字符中插個(gè)字符中插入入j個(gè)加號(hào)能達(dá)到的最小值個(gè)加號(hào)能達(dá)到的最小值,最后的答最后的答案也就是案也就是Flength(s),m. 于是就有一個(gè)動(dòng)規(guī)的方程于是就有一個(gè)動(dòng)規(guī)的方程: Fi,j:=min(fi,j,fk,j-

24、1+numk+1,i) numk+1,i表示表示k+1位到位到i位所形成的數(shù)字位所形成的數(shù)字.這里顯然這里顯然是把加號(hào)插入了第是把加號(hào)插入了第k+1個(gè)位置上個(gè)位置上. 知道了這一題怎么做以后知道了這一題怎么做以后,乘積最大乘積最大的一題也是完全一樣的形式的一題也是完全一樣的形式,誰(shuí)還會(huì)誰(shuí)還會(huì)去用搜索去用搜索?定量定量 現(xiàn)在大概大家已經(jīng)了解了定量現(xiàn)在大概大家已經(jīng)了解了定量是什么是什么,那么我們下面通過(guò)幾那么我們下面通過(guò)幾道題目來(lái)了解一下定量的威力道題目來(lái)了解一下定量的威力.游戲游戲 游戲游戲(Noip2003普及組普及組) 這一題的描述簡(jiǎn)單說(shuō)一下這一題的描述簡(jiǎn)單說(shuō)一下:在一在一個(gè)圈的周圍有個(gè)圈的

25、周圍有n個(gè)石子個(gè)石子,將他們劃將他們劃分成分成m堆堆(每堆中的石子必須連續(xù)每堆中的石子必須連續(xù)相鄰相鄰),每一堆石子計(jì)算出他們的每一堆石子計(jì)算出他們的總重量總重量mod10的值的值,然后將這些然后將這些值相乘值相乘,求得到的結(jié)果最大最小求得到的結(jié)果最大最小值是多少值是多少.游戲游戲 這一題作者其實(shí)是根據(jù)最佳加這一題作者其實(shí)是根據(jù)最佳加法表達(dá)式改編的法表達(dá)式改編的.但是他加了一但是他加了一個(gè)在圈上的條件個(gè)在圈上的條件,怎么辦呢怎么辦呢?尋找定量!游戲游戲 可想而知可想而知,因?yàn)橹辽僖殖梢驗(yàn)橹辽僖殖?堆堆,那那么至少有兩個(gè)石子之間是會(huì)被分隔么至少有兩個(gè)石子之間是會(huì)被分隔開的開的.這就是定量這就

26、是定量!當(dāng)劃分?jǐn)?shù)當(dāng)劃分?jǐn)?shù)1時(shí)時(shí),一一定有兩個(gè)相鄰石子被劃分到不同的定有兩個(gè)相鄰石子被劃分到不同的堆里去堆里去! 于是這個(gè)圈被這樣的理解斷成了一于是這個(gè)圈被這樣的理解斷成了一條線條線,解法就和最佳加法表達(dá)式一解法就和最佳加法表達(dá)式一樣了樣了. 當(dāng)然這個(gè)斷開的位置是需要枚舉的當(dāng)然這個(gè)斷開的位置是需要枚舉的,然后保留下一個(gè)最優(yōu)值然后保留下一個(gè)最優(yōu)值.顯然這個(gè)顯然這個(gè)斷開的操作對(duì)整個(gè)過(guò)程沒(méi)有影響斷開的操作對(duì)整個(gè)過(guò)程沒(méi)有影響,因?yàn)檫@是必然的情況因?yàn)檫@是必然的情況,這是定量這是定量!最優(yōu)三角形劃分最優(yōu)三角形劃分 問(wèn)題描述問(wèn)題描述 給定一具有給定一具有N N（N50N50）個(gè)頂點(diǎn)）個(gè)頂點(diǎn)( (從從1 1到到

27、N N編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問(wèn)如何把這個(gè)凸多邊的權(quán)均已知。問(wèn)如何把這個(gè)凸多邊形劃分成形劃分成N-2N-2個(gè)互不相交的三角形，個(gè)互不相交的三角形，使得這些三角形頂點(diǎn)的權(quán)的乘積之使得這些三角形頂點(diǎn)的權(quán)的乘積之和最??？和最??？ 最優(yōu)三角形劃分最優(yōu)三角形劃分 這一題大概搜都是十分麻煩的這一題大概搜都是十分麻煩的,可是可是這一題這一題Dp的話的話,比搜索要容易實(shí)現(xiàn)和比搜索要容易實(shí)現(xiàn)和容易理解得多容易理解得多. 先得表示一下狀態(tài)先得表示一下狀態(tài),我們用我們用fi,j表示表示以第以第i個(gè)點(diǎn)開頭個(gè)點(diǎn)開頭,順時(shí)針長(zhǎng)度為順時(shí)針長(zhǎng)度為j的一的一塊子多邊形塊子多邊形.如上圖中

28、如上圖中f1,5表示的表示的子多邊形子多邊形(黑色虛線劃開黑色虛線劃開)最優(yōu)三角形劃分最優(yōu)三角形劃分 如果沒(méi)有紅色虛線的部分如果沒(méi)有紅色虛線的部分,或許你或許你會(huì)認(rèn)為決策應(yīng)該是枚舉子多邊形內(nèi)會(huì)認(rèn)為決策應(yīng)該是枚舉子多邊形內(nèi)的兩點(diǎn)連線的兩點(diǎn)連線,然后分成兩個(gè)子多邊然后分成兩個(gè)子多邊形形.這顯然是不行的這顯然是不行的,因?yàn)橛?jì)算機(jī)已因?yàn)橛?jì)算機(jī)已經(jīng)無(wú)法再表示分割出來(lái)的子多邊形經(jīng)無(wú)法再表示分割出來(lái)的子多邊形了了(不能用不能用fi,j來(lái)表示了來(lái)表示了).最優(yōu)三角形劃分最優(yōu)三角形劃分 那么我們?cè)撊绾螞Q策呢那么我們?cè)撊绾螞Q策呢?尋找定量尋找定量! 顯然可以發(fā)現(xiàn)顯然可以發(fā)現(xiàn),fi,j表示的子多邊形表示的子多邊形有

29、一條邊是在內(nèi)部的有一條邊是在內(nèi)部的(黑色虛線黑色虛線),而這而這一條邊在該子多邊形內(nèi)必定屬于某個(gè)一條邊在該子多邊形內(nèi)必定屬于某個(gè)三角形三角形,因?yàn)槲覀冞x擇了該子多邊形作因?yàn)槲覀冞x擇了該子多邊形作為一種狀態(tài)為一種狀態(tài),那么就一定存在那條虛線那么就一定存在那條虛線黑邊黑邊,所以一定存在所說(shuō)的三角形所以一定存在所說(shuō)的三角形.于于是我們枚舉這個(gè)三角形的另外一個(gè)點(diǎn)是我們枚舉這個(gè)三角形的另外一個(gè)點(diǎn)在子多邊形的位置在子多邊形的位置,則可以把子問(wèn)題還則可以把子問(wèn)題還原到原問(wèn)題原到原問(wèn)題(因?yàn)樵撊切伟讯噙呅蝿澮驗(yàn)樵撊切伟讯噙呅蝿澇闪藘蓚€(gè)可以用表示的多邊形和一個(gè)成了兩個(gè)可以用表示的多邊形和一個(gè)三角形三角形).

30、這些再次分割出的子多邊形這些再次分割出的子多邊形就是以前狀態(tài)就是以前狀態(tài),而剛才的多邊形則是當(dāng)而剛才的多邊形則是當(dāng)前狀態(tài)前狀態(tài).定量定量 其實(shí)定量的作用就是為了寫出其實(shí)定量的作用就是為了寫出狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程,即讓人能迅速找即讓人能迅速找出狀態(tài)之間的關(guān)系出狀態(tài)之間的關(guān)系(決策決策).通過(guò)通過(guò)定量的處理定量的處理,當(dāng)前狀態(tài)又回到了當(dāng)前狀態(tài)又回到了以前狀態(tài)以前狀態(tài),選手就可以知道選手就可以知道,這這一題就是要用動(dòng)態(tài)規(guī)劃來(lái)求解一題就是要用動(dòng)態(tài)規(guī)劃來(lái)求解了了.定量定量 我們來(lái)看看剛才的一些題目的定量我們來(lái)看看剛才的一些題目的定量. 交錯(cuò)匹配交錯(cuò)匹配:一定存在最后一組交錯(cuò)一定存在最后一組交錯(cuò)(這好

31、這好像是廢話像是廢話),所以枚舉這個(gè)最后的交錯(cuò)的所以枚舉這個(gè)最后的交錯(cuò)的位置作為狀態(tài)位置作為狀態(tài),這樣就回到以前狀態(tài)這樣就回到以前狀態(tài). 買車票買車票:定量定量1:一定有最后一個(gè)車站一定有最后一個(gè)車站(這這個(gè)作為狀態(tài)個(gè)作為狀態(tài));定量定量2:某個(gè)車站一定是由某個(gè)車站一定是由某個(gè)前面的車站到達(dá)的某個(gè)前面的車站到達(dá)的.(導(dǎo)彈攔截也是導(dǎo)彈攔截也是這樣這樣) 數(shù)字三角形數(shù)字三角形:某個(gè)點(diǎn)一定是由他上面的某個(gè)點(diǎn)一定是由他上面的相鄰兩點(diǎn)到達(dá)的相鄰兩點(diǎn)到達(dá)的.(過(guò)河卒也是這樣過(guò)河卒也是這樣)定量很不錯(cuò)啊!動(dòng)態(tài)規(guī)劃的武器動(dòng)態(tài)規(guī)劃的武器 在動(dòng)規(guī)的操作過(guò)程中在動(dòng)規(guī)的操作過(guò)程中,或者是操或者是操作過(guò)程前作過(guò)程前,有

32、一些很常用的武器有一些很常用的武器,這里簡(jiǎn)要介紹兩種這里簡(jiǎn)要介紹兩種:排序排序 武器一武器一:排序排序 遇到過(guò)很多需要排序的動(dòng)態(tài)規(guī)遇到過(guò)很多需要排序的動(dòng)態(tài)規(guī)劃題目劃題目,如果不排序如果不排序,動(dòng)規(guī)的思動(dòng)規(guī)的思想很難體現(xiàn)想很難體現(xiàn).TomTom的煩惱的煩惱 Tom的煩惱的煩惱 這是大家熟知的一題這是大家熟知的一題,如果不如果不排序的話排序的話,復(fù)雜度便是復(fù)雜度便是N2,按按起始時(shí)間排序復(fù)雜度也是起始時(shí)間排序復(fù)雜度也是N2,二按結(jié)束時(shí)間排序之后復(fù)雜度二按結(jié)束時(shí)間排序之后復(fù)雜度降為了降為了NlogN.巴比倫塔巴比倫塔 巴比倫塔巴比倫塔 問(wèn)題描述問(wèn)題描述: 有很多的不同種類的立方體有很多的不同種類的立

33、方體(長(zhǎng)寬高不同長(zhǎng)寬高不同),每一類有無(wú)限多每一類有無(wú)限多個(gè)個(gè).將他們一層層的疊加起來(lái)將他們一層層的疊加起來(lái),要要求上面的一塊立方體的下底面一求上面的一塊立方體的下底面一定要比下面的一塊立方體的上底定要比下面的一塊立方體的上底面要小面要小,就是長(zhǎng)和寬都要小于就是長(zhǎng)和寬都要小于.問(wèn)問(wèn)最多能建成多高的塔最多能建成多高的塔.巴比倫塔巴比倫塔 經(jīng)過(guò)研究可以發(fā)現(xiàn)經(jīng)過(guò)研究可以發(fā)現(xiàn),每一種類的立方每一種類的立方體有體有3種不同的擺放方式種不同的擺放方式,而每種擺而每種擺放方式最多用放方式最多用1次次,所以可以分離出所以可以分離出3*N塊塊“不同不同”的立方體的立方體,接下來(lái)接下來(lái),或或許你仍然不知道如何動(dòng)規(guī)

34、許你仍然不知道如何動(dòng)規(guī),那么就試那么就試試排序試排序.列出所有的石塊的所有擺放列出所有的石塊的所有擺放方式方式xi,yi,zi.xi,yi,zi.必須全部保證必須全部保證xiyixiyi.xiyi.然后按關(guān)鍵字然后按關(guān)鍵字xi,yi,zixi,yi,zi的大小順序排序的大小順序排序. .這樣就可以進(jìn)行十這樣就可以進(jìn)行十分簡(jiǎn)單的類似與導(dǎo)彈攔截的一個(gè)動(dòng)分簡(jiǎn)單的類似與導(dǎo)彈攔截的一個(gè)動(dòng)態(tài)規(guī)劃的處理了態(tài)規(guī)劃的處理了. .限制條件是限制條件是xixi和和yi,yi,代價(jià)值是代價(jià)值是zi(zi(高度高度).).滑雪滑雪 滑雪滑雪(上海上海2002) 題目的大意是給出一個(gè)矩陣題目的大意是給出一個(gè)矩陣,如如:對(duì)

35、于所給出的矩陣找出一條最長(zhǎng)的遞減鏈,滿足鏈中相鄰的兩個(gè)元素間都是在矩陣中相鄰的.上圖中所給出的矩陣中的最長(zhǎng)鏈?zhǔn)? 2 3 425.滑雪滑雪 對(duì)于有給出的數(shù)字進(jìn)行遞減排序?qū)τ谟薪o出的數(shù)字進(jìn)行遞減排序,然后兩重循環(huán)就搞定問(wèn)題然后兩重循環(huán)就搞定問(wèn)題.動(dòng)態(tài)動(dòng)態(tài)轉(zhuǎn)移方程是轉(zhuǎn)移方程是: Fi:=max(Fi,Fj+1); 滿足條件是滿足條件是i與與j在原矩陣中相在原矩陣中相鄰鄰. 試想試想,如果你不知道要排序如果你不知道要排序,你能你能想到這題是用動(dòng)態(tài)規(guī)劃嗎想到這題是用動(dòng)態(tài)規(guī)劃嗎?填鴨填鴨 武器二武器二:填鴨填鴨 這個(gè)思想帶有枚舉的感覺(jué)這個(gè)思想帶有枚舉的感覺(jué).就是就是開個(gè)大數(shù)組開個(gè)大數(shù)組,把代價(jià)值一個(gè)個(gè)填

36、把代價(jià)值一個(gè)個(gè)填進(jìn)去進(jìn)去.硬幣問(wèn)題硬幣問(wèn)題 硬幣問(wèn)題（經(jīng)典問(wèn)題）硬幣問(wèn)題（經(jīng)典問(wèn)題） 就是給出就是給出n種硬幣的面值種硬幣的面值,問(wèn)面值問(wèn)面值 M有有多少種不同的表示方法多少種不同的表示方法. 動(dòng)態(tài)轉(zhuǎn)移方程是動(dòng)態(tài)轉(zhuǎn)移方程是Fi:=Fi+FI-costj.當(dāng)前狀態(tài)是當(dāng)前狀態(tài)是i,以前狀態(tài)是以前狀態(tài)是i-costj. 多米諾骨牌（某題的簡(jiǎn)化）多米諾骨牌（某題的簡(jiǎn)化） 有有N張多米諾骨牌張多米諾骨牌,每張的兩端有兩個(gè)每張的兩端有兩個(gè)數(shù)字?jǐn)?shù)字,范圍在范圍在1.6之間之間.每張骨牌可以正每張骨牌可以正放放,也可以反放也可以反放.求出一種擺放的情況求出一種擺放的情況,使使得所有的骨牌上端數(shù)字之和與下端數(shù)字

37、得所有的骨牌上端數(shù)字之和與下端數(shù)字之和的差值最小之和的差值最小.求出最小差值求出最小差值.多米諾骨牌多米諾骨牌可以這么考慮這個(gè)問(wèn)題可以這么考慮這個(gè)問(wèn)題:我們把每一個(gè)骨牌的上下差值記我們把每一個(gè)骨牌的上下差值記下。接下來(lái)的任務(wù)便是將這些值下。接下來(lái)的任務(wù)便是將這些值分成兩組，使得他們的和的差值分成兩組，使得他們的和的差值最小。動(dòng)規(guī)過(guò)程如下：最小。動(dòng)規(guī)過(guò)程如下：f0:=true; for i:=1 to n do for j:=sum downto ai do fj:=fj or fj-ai;Sum表示所有差值的和表示所有差值的和. ai表示第表示第i塊骨牌塊骨牌的差值的差值. J是當(dāng)前狀態(tài)是當(dāng)前

38、狀態(tài),j-ai是以前狀態(tài)是以前狀態(tài).fj表示表示j這個(gè)差值能否通過(guò)組合得到。這個(gè)差值能否通過(guò)組合得到。接下來(lái)的程序就不用我多說(shuō)了。接下來(lái)的程序就不用我多說(shuō)了。商店購(gòu)物商店購(gòu)物 商店購(gòu)物商店購(gòu)物(IOI)(IOI) 這一題更是需要開一個(gè)五維這一題更是需要開一個(gè)五維boolbool型數(shù)組型數(shù)組. .還需要通過(guò)遞歸還需要通過(guò)遞歸求出組合形式求出組合形式. .動(dòng)規(guī)的方程我動(dòng)規(guī)的方程我就不寫了就不寫了. .動(dòng)態(tài)規(guī)劃的武器動(dòng)態(tài)規(guī)劃的武器|講完了比較實(shí)用的兩種種動(dòng)規(guī)的武器之后,我們來(lái)看看一些大家可能不太會(huì)做的動(dòng)規(guī)類型特殊的動(dòng)規(guī)特殊的動(dòng)規(guī) 這里我講講三種特殊的動(dòng)態(tài)規(guī)這里我講講三種特殊的動(dòng)態(tài)規(guī)劃劃:圖狀動(dòng)規(guī)圖狀

39、動(dòng)規(guī),樹狀動(dòng)規(guī)樹狀動(dòng)規(guī),二次動(dòng)二次動(dòng)規(guī)規(guī).圖狀動(dòng)規(guī)圖狀動(dòng)規(guī) 城堡城堡 某國(guó)聰明美麗的公主要找一位如意郎君，某國(guó)聰明美麗的公主要找一位如意郎君，她希望未來(lái)的夫君是一個(gè)聰明善良，節(jié)她希望未來(lái)的夫君是一個(gè)聰明善良，節(jié)儉但又不吝嗇的人。為了找到理想的人儉但又不吝嗇的人。為了找到理想的人選，她的爸爸選，她的爸爸國(guó)王，給她修建了一座國(guó)王，給她修建了一座城堡，這個(gè)城堡有很多房間，房間之間城堡，這個(gè)城堡有很多房間，房間之間有走廊連接，但每進(jìn)入一個(gè)房間必須要有走廊連接，但每進(jìn)入一個(gè)房間必須要花費(fèi)一定數(shù)量的錢幣，公主就在某個(gè)房花費(fèi)一定數(shù)量的錢幣，公主就在某個(gè)房間中等待。開始，國(guó)王給每個(gè)候選人一間中等待。開始，國(guó)王

40、給每個(gè)候選人一樣多的錢幣，候選人從同一個(gè)地點(diǎn)出發(fā)，樣多的錢幣，候選人從同一個(gè)地點(diǎn)出發(fā)，直到找到美麗的公主為止，如果這時(shí)哪直到找到美麗的公主為止，如果這時(shí)哪個(gè)人找到了公主，并且錢幣剛好用完，個(gè)人找到了公主，并且錢幣剛好用完，那么他將會(huì)贏得公主的芳心。那么他將會(huì)贏得公主的芳心。城堡城堡 乍看此題乍看此題,似乎就是搜沒(méi)得說(shuō)了似乎就是搜沒(méi)得說(shuō)了,是嗎是嗎? 如果告訴你這一題是動(dòng)態(tài)規(guī)劃如果告訴你這一題是動(dòng)態(tài)規(guī)劃的話的話,你會(huì)怎么做你會(huì)怎么做?狀態(tài)是什狀態(tài)是什么動(dòng)態(tài)轉(zhuǎn)移方程是什么么動(dòng)態(tài)轉(zhuǎn)移方程是什么?城堡城堡 既然是問(wèn)我們能不能到達(dá)既然是問(wèn)我們能不能到達(dá),所以所以想想就應(yīng)該知道想想就應(yīng)該知道,動(dòng)規(guī)的數(shù)組是

41、動(dòng)規(guī)的數(shù)組是bool型的型的.一開始時(shí)一開始時(shí),只有出發(fā)的只有出發(fā)的房間記為房間記為true. 但是但是,并不是以每個(gè)房間作為狀并不是以每個(gè)房間作為狀態(tài)態(tài),因?yàn)檫€存在一個(gè)把錢用光的因?yàn)檫€存在一個(gè)把錢用光的問(wèn)題問(wèn)題.到達(dá)同一個(gè)房間時(shí)到達(dá)同一個(gè)房間時(shí),如果如果剩余的錢不一樣剩余的錢不一樣,也就會(huì)有不同也就會(huì)有不同的決策的決策. 所以狀態(tài)就是在剩余所以狀態(tài)就是在剩余j個(gè)錢幣的個(gè)錢幣的時(shí)候能否到達(dá)第時(shí)候能否到達(dá)第i個(gè)房間個(gè)房間.用用fi,j來(lái)表示來(lái)表示.圖狀動(dòng)規(guī)圖狀動(dòng)規(guī)于是動(dòng)態(tài)轉(zhuǎn)移方程也就出來(lái)了于是動(dòng)態(tài)轉(zhuǎn)移方程也就出來(lái)了K表示的是和I連接的一個(gè)房間,ci表示進(jìn)入I號(hào)房間的花費(fèi).樹狀動(dòng)規(guī)樹狀動(dòng)規(guī) 沒(méi)有上司的晚會(huì)沒(méi)有上司的晚會(huì) 某公司要舉辦一次晚會(huì)，但是為某公司要舉辦一次晚會(huì)，但是為了使得晚會(huì)的氣氛更加活躍，每了使得晚會(huì)的氣氛更加活躍，每個(gè)參加晚會(huì)的人都不希望在晚會(huì)個(gè)參加晚會(huì)的人都不希望在