noip動(dòng)態(tài)規(guī)劃講解ppt課件(存儲(chǔ)版)
【正文】 方格中則放入數(shù)字 0。 我們來驗(yàn)證一下： X Y Z X坐標(biāo) （ 3， 3） 3+3=6 Y坐標(biāo)（ 3， 4） 3+4=7 Z坐標(biāo)（ 4， 4） 4+4=8 X、 Y、Z的坐標(biāo)和在不斷增加，每次 +1。 Inc(f[x,i,j],a[xj,j])。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。 【 輸入數(shù)據(jù) 】 第一行為石子堆數(shù) N。 (i=kj) f[i,j]:=Min(f[i,k],f[k+1,j]}+ 而 f[i,i]和一段石子的總和是可以預(yù)處理的，只要將石子序列倍長(zhǎng)，復(fù)雜度 O(n^3)，此題就能順利 AC了。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。則第 1兩顆珠子聚合后釋放的能量為(4⊕ 1)=10*2*3=60。 對(duì)于題目中所說的具有很強(qiáng)枚舉意味的變量（如 k段， n次等），一般將其放入狀態(tài)中枚舉。要求輸出最大的個(gè)數(shù)。明顯第 1~3之間有 1個(gè)單詞，而 1~4之間呢？ 1~3有的它肯定也有，再去枚舉單詞中有沒有是 cabc后綴的單詞。 【 限制 】 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ù)的一段，每次加入頭或尾。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。所有相鄰的整數(shù)之間用一個(gè)空格隔開。 我們可以發(fā)現(xiàn)題目的一個(gè)玄機(jī)：雖然 L很大，但是M卻很小，也就是說： 石子稀疏對(duì)我們解題有什么幫助呢？我們來看一下下面的推斷： 第一種情況： 當(dāng) s=t時(shí)，很簡(jiǎn)單，青蛙踩到的石頭肯定是 s的倍數(shù)，那么只要統(tǒng)計(jì)一下所有石子中有多少是 s的倍數(shù)，輸出即可。所以，只有當(dāng) t=s+1時(shí)，連續(xù)的點(diǎn)的起始位置才能盡量后面。 1， 1， 5。此類問題一般要用到數(shù)學(xué)公式、數(shù)學(xué)證明、方程變形、極端化等思想，根據(jù)題目的不同適當(dāng)選取方法。 f[i,j]:=f[ij,1]+f[ij,2]+f[ij,3]+…+f[i j,j1]+f[ij,j]。 ∴ f[i,j]:=f[ij,1]+f[ij,2]…+f[i j,j1]+f[ij,j] =f[i1,j1]+f[ij,j]。 因?yàn)榇祟}給我們的是中序遍歷，所以如果 a[i]為根，那么 a[1]~a[i1]就是這棵樹的左子樹， a[i+1]~a[n]就是這棵樹的右子樹。動(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了。 要求輸出； （ 1） tree的最高加分 （ 2） tree的前序遍歷 【輸入格式】 第 1行：一個(gè)整數(shù) n（ n＜ 30）， 為節(jié)點(diǎn)個(gè)數(shù)。 觀察下面的變形： f[i,j]:=f[ij,1]+f[ij,2]…+f[i j,j]。通過類推，小狀態(tài)可以分成更小的狀態(tài)。在 NOIp中數(shù)學(xué)遞推題并不常見，但不能排除它出現(xiàn)的可能性。至此，過河完美 AC！ Sample Problem14 數(shù)的劃分（ NOIp2022） 【 問題描述 】 將整數(shù) n分成 k份，且每份不能為空，任意兩份不能相同 (不考慮順序 )。 所以當(dāng) s=4， t=5時(shí)，如果一段沒有石頭的區(qū)間長(zhǎng)度在4*5=20以外，那么我們只要遞推前 20就可以了，因?yàn)?20后面的情況是一樣的（仔細(xì)想想為什么？）。所以，這種方法需要進(jìn)行改進(jìn)。第二行有三個(gè)正整數(shù) S， T， M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中 1 = S = T = 10， 1 = M = 100。由于橋的長(zhǎng)度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)： 0， 1， …… ， L（其中 L是橋的長(zhǎng)度）。 【 輸入 】 第一行為兩個(gè)用空格隔開的整數(shù) n和 m。令 s[i,j]表示 i~j之間有多少個(gè)單詞，那么s[i,j]=s[i,j1]+以第 j位為結(jié)尾，包含在 i~j這段串里的單詞個(gè)數(shù)。 例如字符串 this中可包含 this和 is，選用 this之后就不能包含 th)。 通過剛才的石子歸并思想，我們可以用 f[i,j]表示前 i個(gè)數(shù)字我分了 j段所能得到的最大值，那么 f[i,j]就可以從f[k,j1]（前 k個(gè)數(shù)字分成了 j1段）推來，因?yàn)?f[i,j]就是f[k,j1]和（ k+1~i）這段數(shù)字串的乘積。 例如：設(shè) N=4， 4顆珠子的頭標(biāo)記與尾標(biāo)記依次為 (2， 3) (3， 5) (5， 10) (10， 2)。 Sample Problem9 能量項(xiàng)鏈（ NOIp2022） 在 Mars星球上，每個(gè) Mars人都隨身佩帶著一串能量項(xiàng)鏈。只要在所有的 f[i,k]+f[k+1,j]中取個(gè)最小值（就是原來此次沒歸并前的最小值），加上自己本身所有石子的和（因?yàn)闅w并一次的代價(jià)是所有石子的總和），就是我們要求的 f[i,j]?，F(xiàn)在，請(qǐng)你幫助小淵和小軒找到這樣的兩條路徑。幸運(yùn)的是，他們可以通過傳紙條來進(jìn)行交流。 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[i,j]是從 f[i1,j]或者 f[i,j1]走來。枚舉的復(fù)雜度是 ，盡管 n、 m很小，但是在大 DFS的前提下就不怎么劃算了。 End。 Sample Problem4 【輸入文件】 第 1行，為兩個(gè)正整數(shù) N m（ 其中 N（ 32022） 表示總錢數(shù)， m（ 60） 為希望購買物品的個(gè)數(shù)。每個(gè)主件可以有 0個(gè)、 1個(gè)或 2個(gè)附件。 完全背包： 有 N種物品和一個(gè)容量為 V的背包，每種物品都有無限件可用。 Sample Problem2 攔截導(dǎo)彈 （ NOIp1999） 某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊 ， 發(fā)展出一種導(dǎo)彈攔截系統(tǒng) 。最長(zhǎng)的不下降序列就是求長(zhǎng)度最長(zhǎng)的子序列 。歷屆 NOIp動(dòng)態(tài)規(guī)劃講解
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1