【正文】 第 2行： n個(gè)用空格隔開(kāi)的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)＜ 100）。 一般地， f[i,j]就可以分成 f[ij,1]、 f[ij,2]、 f[ij,3]等小狀態(tài)，而 f[i,j]的種數(shù)就是小狀態(tài)的總合。例如： n=7， k=3， 下面三種分法被認(rèn)為是相同的。而改進(jìn)的方法，就是狀態(tài)壓縮。坐標(biāo)為 0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為 L的點(diǎn)表示橋的終點(diǎn)。 如串 cabce，單詞有 cab、 abc。 于是狀態(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ù)字的值。在項(xiàng)鏈上有 N顆能量珠。 Sample Problem7 Sample Problem8 石子歸并原題 【 題目描述 】 在一個(gè)圓形操場(chǎng)的四周擺放著 N堆石子 (N= 100),現(xiàn)要將石子有次序地合并成一堆 .規(guī)定每次只能選取相鄰的兩堆合并成新的一堆 ,并將新的一堆的石子數(shù) ,記為該次合并的得分 .編一程序 ,由文件讀入堆棧數(shù) N及每堆棧的石子數(shù) (=20). 選擇一種合并石子的方案 ,使用權(quán)得做 N－ 1次合并 ,得分的總和最小。 If i=j Then Inc(f[x,i,j],a[i,xi]) Else Begin Inc(f[x,i,j],a[xi,i])。因此我們使用 DP來(lái)枚舉出所有可能的面額，而方法，就是傳說(shuō)中的完全背包（經(jīng)過(guò)處理的）。）從第 2行到第 m+1行，第 j行給出了編號(hào)為 j1的物品的基本數(shù)據(jù)，每行有 3個(gè)非負(fù)整數(shù) v p q（ 其中 v表示該物品的價(jià)格（ v10000）， p表示該物品的重要度（ 1~5）， q表示該物品是主件還是附件。第 i種物品的費(fèi)用是 c[i]， 價(jià)值是w[i]。 For i:=1 To n Do For j:=1 To i1 Do If (a[i]=a[j])And(f[i]f[j]+1) Then f[i]:=f[j]+1。 若存在 i1i2i3 … ie 且有 a(i1)a(i2) … a(ie)則稱為長(zhǎng)度為 e的不下降序列。第 i件物品的費(fèi)用是 c[i]， 價(jià)值是 w[i]。 設(shè)第 j件物品的價(jià)格為 v[j]， 重要度為 w[j]， 共選中了 k件物品，編號(hào)依次為 j1，j2， …… ， jk， 則所求的總和為： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk] 。那么為什么它出現(xiàn)在動(dòng)態(tài)規(guī)劃的專題中的？是因?yàn)?…… 你 DFS生成一組郵票面值之后，你需要用某種方法把它能達(dá)到的面額都枚舉出來(lái)。 用 f[x,i,j]表示走到第 x步時(shí)，第 1條路線走到橫坐標(biāo)為 i的地方，第 2條路線走到了橫坐標(biāo)為 j的地方。 還有一件事情需要注意，全班每個(gè)同學(xué)愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒(méi)有定義，輸入時(shí)用 0表示），可以用一個(gè) 0100的自然數(shù)來(lái)表示，數(shù)越大表示越好心。 End。 【 輸出 】 輸出所求得的最大乘積（一個(gè)自然數(shù)）。所以第一步刪串。 過(guò)河（ NOIp2022） 【 問(wèn)題描述 】 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。 但是有個(gè)地方我們忽略了，那就是數(shù)據(jù)規(guī)模。這樣，最大的復(fù)雜度就是 t(t1)*（石頭個(gè)數(shù) +1） =90*101=9090，比之前的復(fù)雜度大大降低。乍一看我們沒(méi)發(fā)現(xiàn)什么規(guī)律，但是這些分割方法都有一個(gè)共同點(diǎn)： 因?yàn)椴辉试S出 現(xiàn) 10=0+10這 種分割，所以 有了這個(gè)性質(zhì)，我們來(lái)嘗試下面的操作：將所有小整數(shù)都減去 1。不考慮它的空 子樹(shù)。 這樣，我們只要枚舉 i~j這個(gè)區(qū)間和枚舉這個(gè)區(qū)間的根 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]。 5， 1， 1。 s=4， t=5。當(dāng)青蛙跳到或跳過(guò)坐標(biāo)為 L的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。 Sample Problem12 矩陣取數(shù)游戲（ NOIp2022） 【 問(wèn)題描述 】 帥帥經(jīng)常更同學(xué)玩一個(gè)矩陣取數(shù)游戲：對(duì)于一個(gè)給定的 n*m的矩陣，矩陣中的每個(gè)元素 aij據(jù)為非負(fù)整數(shù)。 Sample Problem11 統(tǒng)計(jì)單詞個(gè)數(shù)（ NOIp2022） 【 問(wèn)題描述 】 給出一個(gè)長(zhǎng)度不超過(guò) 200的由小寫(xiě)英文字母組成的字母串 (約定 。因?yàn)橹挥羞@樣，通過(guò)吸盤（吸盤是 Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。 【 輸出數(shù)據(jù) 】 一行，最小總和。 End。在走過(guò)的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字 0）。 Ff:=f[ja[i]]+b[i]。 Sample Problem4 金明的預(yù)算方案（ NOIp2022） 【問(wèn)題描述】 金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。 你的任務(wù)是 ， 已知所有 N位同學(xué)的身高 ， 計(jì)算最少需要幾位同學(xué)出列 ， 可以使得剩下的同學(xué)排成合唱隊(duì)形 。近年來(lái)，動(dòng)態(tài)規(guī)劃幾乎每次都出現(xiàn)在 NOIp的賽場(chǎng)上，而且還有越來(lái)越多的趨勢(shì)。 由于該系統(tǒng)還在試用階段 ， 所以只有一套系統(tǒng) ， 因此有可能不能攔截所有的導(dǎo)彈 。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù) 1~5表示，第 5等最重要。 例如， N=3， K=2，如果面值分別為 1分、 4分，則在 1分～ 6分之間的每一個(gè)郵資值都能得到（當(dāng)然還有 8分、 9分和 12分）；如果面值分別為 1分、3分，則在 1分～ 7分之間的每一個(gè)郵資值都能得到。 再觀察，我們發(fā)現(xiàn)，走第 n步時(shí)，能走到點(diǎn)是固定的。 在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。 For i:=1 To n1 Do For j:=1 To 2*ni Do Begin f[j,j+i]:=Maxlongint。 這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為 ((4⊕ 1)⊕ 2)⊕ 3） =10*2*3+10*3*5+10*5*10=710。 【 樣例輸入 】 3 thisisabo