【正文】 至于路徑，記錄一下就可以了。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第 j個節(jié)點的分數(shù)為 di， tree及它的每個子樹都有一個加分，任一棵子樹 subtree（ 也包含 tree本身）的加分計算方法如下： subtree的左子樹的加分 subtree的右子樹的加分＋ subtree的根的分數(shù) 若某個子樹為主，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點本身的分數(shù)。 時間復雜度是你 n*k^2的。 我們先來看一下 f[10,4]的幾種分割方法，如圖：可以看見 10=1+1+3+5=1+2+3+4=2+2+3+3。 問有多少種不同的分法。 因此，我們每次對于一段沒有石頭的區(qū)間長度為 x，如果 x=t(t1)，我們仍然把它當做 x來處理；相反，當xt(t1)時，我們就把它當做 t(t1)處理。 從數(shù)據中我們看到， 12以后的點全部都是可以到達的了。大致代碼如下： For i:=1 To L+t1 Do （仔細想想為什么？） For j:=s To t Do If i這個位子有石頭 Then If f[i]f[ij]+1 Then f[i]:=f[ij]+1 Else If f[i]f[ij] Then f[i]:=f[ij]。 題目給出獨木橋的長度 L，青蛙跳躍的距離范圍 S,T，橋上石子的位置。 這道題目還要高精度，建議寫好非高精的 DP再修 改成高精度的。游戲規(guī)則如下： 1. 每次取數(shù)時須從每行各取走一個元素，共 n個。 首先，題目告訴我們，如果 a是 b的前綴，那么 b肯定沒用了（為什么）。該字串 以每行 20個字母的方式輸入，且保證每行一定為 20個 )。 【 輸入 】 程序的輸入共有兩行： 第一行共有 2個自然數(shù) N， K（ 6≤N≤40， 1≤K≤6） 第二行是一個長度為 N的數(shù)字串。如果前一顆能量珠的頭標記為 m，尾標記為 r，后一顆能量珠的頭標記為 r，尾標記為 n，則聚合后釋放的能量為（ Mars單位），新產生的珠子的頭標記為 m，尾標記為 n。 f[j,j+i]:=f[j,j+i]+Sum[j,j+i]。 【 輸入 】 4 4 5 9 4 【 輸出 】 22 4 5 9 4 5 9 8 總和： 8 9 13 總和： 21 22 總和： 43 我們用 f[i,j]表示以 i堆石子為開頭，以 j堆石子為結尾的一系列石子歸并起來的最小總和。反之亦然。 同樣三取方格數(shù)只要 f[x,i,j,k]用同樣的方法即可。 因此，走到第 n步時， x坐標和 y坐標的和就知道=n+1，這樣我們就不必同時知道 2條路線 x坐標和 y坐標了，知道其中一個 t，另外一個就可以用 n+1t來表示了。 此人從 A點到 B 點共走兩次，試找出 2條這樣的路徑，使得取得的數(shù)之和為最大。 【 樣例 】 INPUT N=3 K=2 OUTPUT 1 3 MAX=7 如果你一看到這道題目就想到搜索，那么 這道題目就是搜索。 01 If j+s[i,1,1]=m Then If Ff+s[i,1,2]f[j+s[i,1,1]] Then f[j+s[i,1,1]]:=Ff+s[i,1,2]。他希望在不超過 N元（可以等于 N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過 N元錢就行”。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（ 最多能攔截的導彈數(shù) ） 2（ 要攔截所有導彈最少要配備的系統(tǒng)數(shù) ） Sample Problem3 反例： 9 8 7 1 10 6 5 4 9 8 7 1 10 6 5 4 9 8 7 1 10 6 5 1 10 1 10 10 9 8 7 1 10 6 5 4 1 10 10 6 5 4 01背包： 有 N件物品和一個容量為 V的背包。 【 輸入文件 】 輸入文件第一行是一個整數(shù) N(2=N=100)， 表示同學的總數(shù) 。 動態(tài)規(guī)劃實質： 枚舉 + 遞推 狀態(tài) 狀態(tài)轉移方程 Sample Problem1 1 3 5 9 1 從樹的根到樹的葉節(jié)點，最多能取多少數(shù)？ 貪心 ： 答案錯誤 暴力搜索 ： 如果數(shù)據大會超時 我們先將 NOIp里的動態(tài)規(guī)劃分分類： 最長不降子序列 背包 方格取數(shù) 石子歸并 狀態(tài)壓縮 數(shù)學遞推 順序遞推 設有由 n個不相同的整數(shù)組成的數(shù)列，記為 : a(1)、 a(2)、 …… 、 a(n)且 a(i)a(j) (i， j=n) 例如 3， 18， 7， 14， 10， 12， 23， 41， 16， 24。 動態(tài)規(guī)劃是信息學競賽中選手必須熟練掌握的一種算法 ,它以其多元性廣受出題者的喜愛。 合唱隊形 （ NOIp2022） 【 問題描述 】 N位同學站成一排 ， 音樂老師要請其中的 (NK)位同學出列 ， 使得剩下的 K位同學排成合唱隊形 。 某天 ， 雷達捕捉到敵國的導彈來襲 。 求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。金明想買的東西很多，肯定會超過媽媽限定的 N元。如果 q=0， 表示該物品為主件，如果 q0， 表示該物品為附件， q是所屬主件的編號） 【輸出文件】 只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值。 Sample Problem5 郵票面值設計（ NOIp1999） 給定一個信封，最多只允許粘貼 N張郵票，計算在給定 K（ N+K≤40）種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設計郵票的面值，能得到最大值 MAX，使在 1～ MAX之間的每一個郵資值都能得到。 Sample Problem6 方格取數(shù) （ NOIp2022） 設有 N*N的方格圖 (N=10,我們將其中的某些方格中填入正整數(shù) ,而其他的