noip動態(tài)規(guī)劃講解ppt課件-文庫吧資料
2025-05-11 18:15本頁面
【正文】 [i,j]表示 i~j之間有多少個單詞，那么s[i,j]=s[i,j1]+以第 j位為結(jié)尾，包含在 i~j這段串里的單詞個數(shù)。所以第一步刪串。預處理出 i~j之間有多少單詞，其實也可以用 DP。要求輸出最大的個數(shù)。 例如字符串 this中可包含 this和 is，選用 this之后就不能包含 th)。要求將此字母串分 成 k份 (1k=40)，且每份中包含的單詞個數(shù)加起來總數(shù)最大 (每份中包含的單詞可以部分重疊。 Sample Problem11 統(tǒng)計單詞個數(shù)（ NOIp2022） 【 問題描述 】 給出一個長度不超過 200的由小寫英文字母組成的字母串 (約定 。 對于題目中所說的具有很強枚舉意味的變量（如 k段， n次等），一般將其放入狀態(tài)中枚舉。 通過剛才的石子歸并思想，我們可以用 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ù)字串的乘積。 【 輸出 】 輸出所求得的最大乘積（一個自然數(shù)）。 Sample Problem10 乘積最大（ NOIp2022） 【 問題描述 】 設有一個長度為 N的數(shù)字串，要求選手使用 K個乘號將它分成 K+1個部分，找出一種分法，使得這 K+1個部分的乘積能夠為最大。則第 1兩顆珠子聚合后釋放的能量為(4⊕ 1)=10*2*3=60。 例如：設 N=4， 4顆珠子的頭標記與尾標記依次為 (2， 3) (3， 5) (5， 10) (10， 2)。 需要時， Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。因為只有這樣，通過吸盤（吸盤是 Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數(shù)。 Sample Problem9 能量項鏈（ NOIp2022） 在 Mars星球上，每個 Mars人都隨身佩帶著一串能量項鏈。 End。 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]。 (i=kj) f[i,j]:=Min(f[i,k],f[k+1,j]}+ 而 f[i,i]和一段石子的總和是可以預處理的，只要將石子序列倍長，復雜度 O(n^3)，此題就能順利 AC了。只要在所有的 f[i,k]+f[k+1,j]中取個最小值（就是原來此次沒歸并前的最小值），加上自己本身所有石子的和（因為歸并一次的代價是所有石子的總和），就是我們要求的 f[i,j]。 因為題目中說，只能歸并相鄰的兩堆石子。 【 輸出數(shù)據(jù) 】 一行，最小總和。 【 輸入數(shù)據(jù) 】 第一行為石子堆數(shù) N?，F(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑。 還有一件事情需要注意，全班每個同學愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用 0表示），可以用一個 0100的自然數(shù)來表示，數(shù)越大表示越好心。班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。幸運的是，他們可以通過傳紙條來進行交流。 傳紙條（ NOIp2022） 【 問題描述 】 小淵和小軒是好朋友也是同班同學，他們在一起總有談不完的話題。 End。 Inc(f[x,i,j],a[xj,j])。 For x:=3 To m+n Do For i:=1 To Min(x,n) Do For j:=1 To Min(x,n) Do Begin f[x,i,j]:=Max(f[x1,i,j],f[x1,i1,j],f[x1,i,j1],f[x1,i1,j1])。 用 f[x,i,j]表示走到第 x步時，第 1條路線走到橫坐標為 i的地方，第 2條路線走到了橫坐標為 j的地方。觀察其坐標我們發(fā)現(xiàn)，第 n步能走到的點其坐標和為 n1。 我們來驗證一下： X Y Z X坐標 （ 3， 3） 3+3=6 Y坐標（ 3， 4） 3+4=7 Z坐標（ 4， 4） 4+4=8 X、 Y、Z的坐標和在不斷增加，每次 +1。 f[i,j]是從 f[i1,j]或者 f[i,j1]走來。 13+14+4+21+15=67 一取方格數(shù)： f[i,j]:=max{f[i1,j],f[i,j1]}。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字 0）。 Sample Problem6 方格取數(shù) （ NOIp2022） 設有 N*N的方格圖 (N=10,我們將其中的某些方格中填入正整數(shù) ,而其他的方格中則放入數(shù)字 0。枚舉的復雜度是 ，盡管 n、 m很小，但是在大 DFS的前提下就不怎么劃算了。那么為什么它出現(xiàn)在動態(tài)規(guī)劃的專題中的？是因為 …… 你 DFS生成一組郵票面值之后，你需要用某種方法把它能達到的面額都枚舉出來。可以驗證當 N=3， K=2時， 7分就是可以得到的連續(xù)的郵資最大值，所以 MAX=7，面值分別為 1分、3分。 Sample Problem5 郵票面值設計（ NOIp1999） 給定一個信封，最多只允許粘貼 N張郵票，計算在給定 K（ N+K≤40）種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設計郵票的面值，能得到最大值 MAX，使在 1～ MAX之間的每一個郵資值都能得到。 End。 10 If j+s[i,2,1]=m Then If Ff+s[i,2,2]f[j+s[i,2,1]] Then f[j+s[i,2,1]]:=Ff+s[i,2,2]。 Ff:=f[ja[i]]+b[i]。如果 q=0， 表示該物品為主件，如果 q0， 表示該物品為附件， q是所屬主件的編號） 【輸出文件】 只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值。 Sample Problem4
教學課件相關(guān)推薦
鄂ICP備17016276號-1