noip動態(tài)規(guī)劃講解ppt課件(編輯修改稿)
2025-06-01 18:15 本頁面
【文章內(nèi)容簡介】 幫忙，那么在小軒遞給小淵的時候就不會再幫忙。反之亦然。 還有一件事情需要注意，全班每個同學(xué)愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用 0表示），可以用一個 0100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高 的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué) 的好心程度只和最大。現(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑。 Sample Problem7 Sample Problem8 石子歸并原題 【 題目描述 】 在一個圓形操場的四周擺放著 N堆石子 (N= 100),現(xiàn)要將石子有次序地合并成一堆 .規(guī)定每次只能選取相鄰的兩堆合并成新的一堆 ,并將新的一堆的石子數(shù) ,記為該次合并的得分 .編一程序 ,由文件讀入堆棧數(shù) N及每堆棧的石子數(shù) (=20). 選擇一種合并石子的方案 ,使用權(quán)得做 N－ 1次合并 ,得分的總和最小。 【 輸入數(shù)據(jù) 】 第一行為石子堆數(shù) N。 第二行為每堆的石子數(shù) ,每兩個數(shù)之間用一個空格分隔。 【 輸出數(shù)據(jù) 】 一行，最小總和。 【 輸入 】 4 4 5 9 4 【 輸出 】 22 4 5 9 4 5 9 8 總和： 8 9 13 總和： 21 22 總和： 43 我們用 f[i,j]表示以 i堆石子為開頭，以 j堆石子為結(jié)尾的一系列石子歸并起來的最小總和。 因為題目中說，只能歸并相鄰的兩堆石子。所以，f[i,j]這一系列石子必然由 f[i,k]和 f[k+1,j]（ i=kj）這兩堆石子歸并而來。只要在所有的 f[i,k]+f[k+1,j]中取個最小值（就是原來此次沒歸并前的最小值），加上自己本身所有石子的和（因為歸并一次的代價是所有石子的總和），就是我們要求的 f[i,j]。 因此，狀態(tài)轉(zhuǎn)移方程為： j Σ n=i a[n]。 (i=kj) f[i,j]:=Min(f[i,k],f[k+1,j]}+ 而 f[i,i]和一段石子的總和是可以預(yù)處理的，只要將石子序列倍長，復(fù)雜度 O(n^3)，此題就能順利 AC了。 For i:=1 To n1 Do For j:=1 To 2*ni Do Begin f[j,j+i]:=Maxlongint。 For k:=j To j+i Do If f[j,j+i]f[j,k]+f[k+1,j+i] Then f[j,j+i]:=f[j,k]+f[k+1,j+i]。 f[j,j+i]:=f[j,j+i]+Sum[j,j+i]。 End。 這樣，求歸并的最大值也是同樣的方法，不再贅述。 Sample Problem9 能量項鏈（ NOIp2022） 在 Mars星球上，每個 Mars人都隨身佩帶著一串能量項鏈。在項鏈上有 N顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應(yīng)著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標記一定等于后一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是 Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為 m，尾標記為 r，后一顆能量珠的頭標記為 r，尾標記為 n，則聚合后釋放的能量為（ Mars單位），新產(chǎn)生的珠子的頭標記為 m，尾標記為 n。 需要時， Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設(shè)計一個聚合順序，使一串項鏈釋放出的總能量最大。 例如：設(shè) N=4， 4顆珠子的頭標記與尾標記依次為 (2， 3) (3， 5) (5， 10) (10， 2)。我們用記號 ⊕ 表示兩顆珠子的聚合操作， (j⊕ k)表示第 j， k兩顆珠子聚合后所釋放的能量。則第 1兩顆珠子聚合后釋放的能量為(4⊕ 1)=10*2*3=60。 這一串項鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為 ((4⊕ 1)⊕ 2)⊕ 3） =10*2*3+10*3*5+10*5*10=710。 Sample Problem10 乘積最大（ NOIp2022） 【 問題描述 】 設(shè)有一個長度為 N的數(shù)字串，要求選手使用 K個乘號將它分成 K+1個部分，找出一種分法，使得這 K+1個部分的乘積能夠為最大。 【 輸入 】 程序的輸入共有兩行： 第一行共有 2個自然數(shù) N， K（ 6≤N≤40， 1≤K≤6） 第二行是一個長度為 N的數(shù)字串。 【 輸出 】 輸出所求得的最大乘積（一個自然數(shù)）。 【 樣例輸入 】 4 2 1231 【 樣例輸出 】 62 這道題目要求把一個長度為 n的數(shù)字串分成 k段，使得每段的乘積最大。 通過剛才的石子歸并思想，我們可以用 f[i,j]表示前 i個數(shù)字我分了 j段所能得到的最大值，那么 f[i,j]就可以從f[k,j1]（前 k個數(shù)字分成了 j1段）推來，因為 f[i,j]就是f[k,j1]和（ k+1~i）這段數(shù)字串的乘積。 于是狀態(tài)轉(zhuǎn)移方程即可得出： f[i,j]:=Max{f[k,j1]*Number[k+1,i]} (j1=ki) 其中 Number[k+1,j]表示數(shù)字串從第 k+1位到第 i位轉(zhuǎn)換成數(shù)字的值。 對于題目中所說的具有很強枚舉意味的變量（如 k段， n次等），一般將其放入狀態(tài)中枚舉。而諸如最大值最小值之類的變量，一般放入數(shù)組中作為值遞推。 Sample Problem11 統(tǒng)計單詞個數(shù)（ NOIp2022） 【 問題描述 】 給出一個長度不超過 200的由小寫英文字母組成的字母串 (約定 。該字串 以每行 20個字母的方式輸入，且保證每行一定為 20個 )。要求將此字母串分 成 k份 (1k=40)，且每份中包含的單詞個數(shù)加起來總數(shù)最大 (每份中包含的單詞可以部分重疊。當選用一個單詞之后，其第一個字母不能再用。 例如字符串 this中可包含 this和 is，選用 this之后就不能包含 th)。單詞在給出 的一個不超過 6個單詞的字典中。要求輸出最大的個數(shù)。 【 樣例輸入 】 3 thisisabookyouareaoh 4 is a ok sab 【 樣例輸出 】 7 this / isabookyoua / reaoh 看到這道題目應(yīng)該
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1