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