【正文】 度，分為5等：用整數(shù) 1~5表示，第 5等最重要。 For i:=1 To n Do For j:=Max Downto a[i] Do (a[i] To Max) If f[j]f[ja[i]]+b[i] Then f[j]:=f[ja[i]]+b[i]。 由于該系統(tǒng)還在試用階段 ， 所以只有一套系統(tǒng) ， 因此有可能不能攔截所有的導(dǎo)彈 。 合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè) K位同學(xué)從左到右依次編號為 1， 2… ， K，他 們 的 身 高 分 別 為 T1， T2， … ， TK， 則 他 們 的 身 高 滿 足T1...TiTi+1… TK(1=i=K)。近年來，動(dòng)態(tài)規(guī)劃幾乎每次都出現(xiàn)在 NOIp的賽場上，而且還有越來越多的趨勢。因此，掌握基本的 NOIp動(dòng)態(tài)規(guī)劃題是至關(guān)重要的。 你的任務(wù)是 ， 已知所有 N位同學(xué)的身高 ， 計(jì)算最少需要幾位同學(xué)出列 ， 可以使得剩下的同學(xué)排成合唱隊(duì)形 。 輸入導(dǎo)彈依次飛來的高度 （ 雷達(dá)給出的高度數(shù)據(jù)是不大于 30000的正整數(shù) ） ，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈 ， 如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng) 。 Sample Problem4 金明的預(yù)算方案（ NOIp2022） 【問題描述】 金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是 10元的整數(shù)倍）。 Ff:=f[ja[i]]+b[i]。可以驗(yàn)證當(dāng) N=3， K=2時(shí)， 7分就是可以得到的連續(xù)的郵資最大值，所以 MAX=7，面值分別為 1分、3分。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字 0）。觀察其坐標(biāo)我們發(fā)現(xiàn)，第 n步能走到的點(diǎn)其坐標(biāo)和為 n1。 End。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時(shí)候幫忙，那么在小軒遞給小淵的時(shí)候就不會(huì)再幫忙。 【 輸出數(shù)據(jù) 】 一行，最小總和。 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]。因?yàn)橹挥羞@樣，通過吸盤（吸盤是 Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。 Sample Problem10 乘積最大（ NOIp2022） 【 問題描述 】 設(shè)有一個(gè)長度為 N的數(shù)字串，要求選手使用 K個(gè)乘號將它分成 K+1個(gè)部分，找出一種分法，使得這 K+1個(gè)部分的乘積能夠?yàn)樽畲蟆? Sample Problem11 統(tǒng)計(jì)單詞個(gè)數(shù)（ NOIp2022） 【 問題描述 】 給出一個(gè)長度不超過 200的由小寫英文字母組成的字母串 (約定 。預(yù)處理出 i~j之間有多少單詞，其實(shí)也可以用 DP。 Sample Problem12 矩陣取數(shù)游戲（ NOIp2022） 【 問題描述 】 帥帥經(jīng)常更同學(xué)玩一個(gè)矩陣取數(shù)游戲：對于一個(gè)給定的 n*m的矩陣，矩陣中的每個(gè)元素 aij據(jù)為非負(fù)整數(shù)。 用 f[i,j,k]表示第 i行，取了一些數(shù)后剩下連續(xù)的一段從 j到 k，那么狀態(tài)轉(zhuǎn)移方程就很好寫了： f[i,j,k]:=Max{f[i,j1,k]+a[j1]*2^(mk+j1) f[i,j,k+1]+a[k+1]*2(mk+j1)}。當(dāng)青蛙跳到或跳過坐標(biāo)為 L的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。 Sample Problem13 此題乍一看上去好像很簡單，因?yàn)橹灰刂嗤芴姆较?，逐步遞推即可。 s=4， t=5。 跟前面的 s=4， t=5的情況一樣，其實(shí) s=9， t=10時(shí)只要一段沒有石頭的區(qū)間長度在 90之外，我們都把它當(dāng)做90對待就可以了。 5， 1， 1。 接下來就是寫出狀態(tài)轉(zhuǎn)移方程了，一旦狀態(tài)轉(zhuǎn)移方程寫出，那么 f[i,j]就可以由 f[x,y]等其他狀態(tài)得來，因?yàn)榈玫阶詈笪覀円蟮?f[n,k]。 For i:=1 To n Do For j:=1 To k Do If i=j Then For t:=1 To j Do f[i,j]:=f[i,j]+f[ij,t]。 最后加點(diǎn)預(yù)處理，此題完美就 AC了！ 反思：解決此類題目，必先學(xué)好數(shù)學(xué)！ Sample Problem15 加分二叉樹（ NOIp2022） 【問題描述】 設(shè)一個(gè) n個(gè)節(jié)點(diǎn)的二叉樹 tree的中序遍歷為（ l,2,3,…,n ）， 其中數(shù)字1,2,3,…, n為節(jié)點(diǎn)編號。 這樣，我們只要枚舉 i~j這個(gè)區(qū)間和枚舉這個(gè)區(qū)間的根 k就可以了。 For i:=1 To n1 Do For j:=1 To ni Do For k:=j To j+i Do If f[j,k1]*f[k+1,j+i]+a[k]f[j,j+i] Then f[j,j+i]:=f[j,k1]*f[k+1,j+i]+a[k]。不考慮它的空 子樹。雖然可以輕松過這題，但如果 n=50000， k=200，這樣的方法就超時(shí)了。乍一看我們沒發(fā)現(xiàn)什么規(guī)律，但是這些分割方法都有一個(gè)共同點(diǎn)： 因?yàn)椴辉试S出 現(xiàn) 10=0+10這 種分割，所以 有了這個(gè)性質(zhì)，我們來嘗試下面的操作：將所有小整數(shù)都減去 1。 【 輸入 】 n， k (6n=200， 2=k=6) 【 輸出 】 一個(gè)整數(shù)，即不同的分法。這樣，最大的復(fù)雜度就是 t(t1)*（石頭個(gè)數(shù) +1） =90*101=9090，比之前的復(fù)雜度大大降低。如果 s=4， t=5，在一段 100000的距離中沒有石頭，其實(shí) 12以后的點(diǎn)都是不用遞推就知道肯定能到達(dá)的。 但是有個(gè)地方我們忽略了，那就是數(shù)據(jù)規(guī)模。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。 過河（ NOIp2022） 【 問題描述 】 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。 m次后取完矩陣所有元素； 2. 每次取走的各個(gè)元素只能是該元素所在行的行首或行尾； 3. 每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分 = 被取走的元素值 *2i，其中 i表示第 i次取數(shù)（從 1開始編號）； 4. 游戲結(jié)束總得分為 m次取數(shù)得分之和。所以第一步刪串。要求將此字母串分 成 k份 (1k=40)，且每份中包含的單詞個(gè)數(shù)加起來總數(shù)最大 (每份中包含的單詞可以部分重疊。 【 輸出 】 輸出所求得的最大乘積（一個(gè)自然數(shù)）。 需要時(shí)， Mars人就