noip動(dòng)態(tài)規(guī)劃講解ppt課件(參考版)
2025-05-08 18:15本頁面
【正文】 動(dòng)態(tài)規(guī)劃的核心就是“狀態(tài)”和“狀態(tài)轉(zhuǎn)移方程”，有了這兩樣?xùn)|西，或許還要再加點(diǎn) DFS、貪心、狀態(tài)壓縮、單調(diào)隊(duì)列等來優(yōu)化動(dòng)態(tài)規(guī)劃，基本上就可以放心 DP了。 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]。 這樣，我們只要枚舉 i~j這個(gè)區(qū)間和枚舉這個(gè)區(qū)間的根 k就可以了。 因?yàn)榇祟}給我們的是中序遍歷，所以如果 a[i]為根，那么 a[1]~a[i1]就是這棵樹的左子樹， a[i+1]~a[n]就是這棵樹的右子樹。 要求輸出； （ 1） tree的最高加分 （ 2） tree的前序遍歷 【輸入格式】 第 1行：一個(gè)整數(shù) n（ n＜ 30）， 為節(jié)點(diǎn)個(gè)數(shù)。不考慮它的空 子樹。 最后加點(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)編號(hào)。 ∴ f[i,j]:=f[ij,1]+f[ij,2]…+f[i j,j1]+f[ij,j] =f[i1,j1]+f[ij,j]。 觀察下面的變形： f[i,j]:=f[ij,1]+f[ij,2]…+f[i j,j]。雖然可以輕松過這題，但如果 n=50000， k=200，這樣的方法就超時(shí)了。 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]。 f[i,j]:=f[ij,1]+f[ij,2]+f[ij,3]+…+f[i j,j1]+f[ij,j]。通過類推，小狀態(tài)可以分成更小的狀態(tài)。乍一看我們沒發(fā)現(xiàn)什么規(guī)律，但是這些分割方法都有一個(gè)共同點(diǎn)： 因?yàn)椴辉试S出 現(xiàn) 10=0+10這 種分割，所以 有了這個(gè)性質(zhì)，我們來嘗試下面的操作：將所有小整數(shù)都減去 1。 接下來就是寫出狀態(tài)轉(zhuǎn)移方程了，一旦狀態(tài)轉(zhuǎn)移方程寫出，那么 f[i,j]就可以由 f[x,y]等其他狀態(tài)得來，因?yàn)榈玫阶詈笪覀円蟮?f[n,k]。此類問題一般要用到數(shù)學(xué)公式、數(shù)學(xué)證明、方程變形、極端化等思想，根據(jù)題目的不同適當(dāng)選取方法。在 NOIp中數(shù)學(xué)遞推題并不常見，但不能排除它出現(xiàn)的可能性。 【 輸入 】 n， k (6n=200， 2=k=6) 【 輸出 】 一個(gè)整數(shù)，即不同的分法。 5， 1， 1。 1， 1， 5。至此，過河完美 AC！ Sample Problem14 數(shù)的劃分（ NOIp2022） 【 問題描述 】 將整數(shù) n分成 k份，且每份不能為空，任意兩份不能相同 (不考慮順序 )。這樣，最大的復(fù)雜度就是 t(t1)*（石頭個(gè)數(shù) +1） =90*101=9090，比之前的復(fù)雜度大大降低。 跟前面的 s=4， t=5的情況一樣，其實(shí) s=9， t=10時(shí)只要一段沒有石頭的區(qū)間長(zhǎng)度在 90之外，我們都把它當(dāng)做90對(duì)待就可以了。所以，只有當(dāng) t=s+1時(shí)，連續(xù)的點(diǎn)的起始位置才能盡量后面。 所以當(dāng) s=4， t=5時(shí)，如果一段沒有石頭的區(qū)間長(zhǎng)度在4*5=20以外，那么我們只要遞推前 20就可以了，因?yàn)?20后面的情況是一樣的（仔細(xì)想想為什么？）。如果 s=4， t=5，在一段 100000的距離中沒有石頭，其實(shí) 12以后的點(diǎn)都是不用遞推就知道肯定能到達(dá)的。 s=4， t=5。 我們可以發(fā)現(xiàn)題目的一個(gè)玄機(jī)：雖然 L很大，但是M卻很小，也就是說： 石子稀疏對(duì)我們解題有什么幫助呢？我們來看一下下面的推斷： 第一種情況： 當(dāng) s=t時(shí)，很簡(jiǎn)單，青蛙踩到的石頭肯定是 s的倍數(shù)，那么只要統(tǒng)計(jì)一下所有石子中有多少是 s的倍數(shù)，輸出即可。所以，這種方法需要進(jìn)行改進(jìn)。 但是有個(gè)地方我們忽略了，那就是數(shù)據(jù)規(guī)模。 Sample Problem13 此題乍一看上去好像很簡(jiǎn)單，因?yàn)橹灰刂嗤芴姆较?，逐步遞推即可。所有相鄰的整數(shù)之間用一個(gè)空格隔開。第二行有三個(gè)正整數(shù) S， T， M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中 1 = S = T = 10， 1 = M = 100。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。當(dāng)青蛙跳到或跳過坐標(biāo)為 L的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。由于橋的長(zhǎng)度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)： 0， 1， …… ， L（其中 L是橋的長(zhǎng)度）。 過河（ NOIp2022） 【 問題描述 】 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。 用 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)}。 【 限制 】 60%的數(shù)據(jù)滿足： 1=n, m=30，答案不超過 10^6 100%的數(shù)據(jù)滿足： 1=n, m=80， 0=aij=1000 改變一下題目的敘述：每行有 m個(gè)數(shù)，倒數(shù)第 i次取的得分是 a[i]*2^(m+1i)；倒推，因?yàn)槊看沃荒苋∫欢沃械念^或尾，所以剩下的永遠(yuǎn)是連續(xù)的一段，每次加入頭或尾。 【 輸入 】 第一行為兩個(gè)用空格隔開的整數(shù) n和 m。 m次后取完矩陣所有元素； 2. 每次取走的各個(gè)元素只能是該元素所在行的行首或行尾； 3. 每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分 = 被取走的元素值 *2i，其中 i表示第 i次取數(shù)（從 1開始編號(hào)）； 4. 游戲結(jié)束總得分為 m次取數(shù)得分之和。 Sample Problem12 矩陣取數(shù)游戲（ NOIp2022） 【 問題描述 】 帥帥經(jīng)常更同學(xué)玩一個(gè)矩陣取數(shù)游戲：對(duì)于一個(gè)給定的 n*m的矩陣，矩陣中的每個(gè)元素 aij據(jù)為非負(fù)整數(shù)。明顯第 1~3之間有 1個(gè)單詞，而 1~4之間呢？ 1~3有的它肯定也有，再去枚舉單詞中有沒有是 cabc后綴的單詞。令 s
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1