《noip動(dòng)態(tài)規(guī)劃講解》ppt課件(文件)
【正文】 20后面的情況是一樣的（仔細(xì)想想為什么？）。 跟前面的 s=4， t=5的情況一樣，其實(shí) s=9， t=10時(shí)只要一段沒有石頭的區(qū)間長(zhǎng)度在 90之外，我們都把它當(dāng)做90對(duì)待就可以了。至此，過河完美 AC！ Sample Problem14 數(shù)的劃分（ NOIp2022） 【 問題描述 】 將整數(shù) n分成 k份，且每份不能為空，任意兩份不能相同 (不考慮順序 )。 5， 1， 1。在 NOIp中數(shù)學(xué)遞推題并不常見，但不能排除它出現(xiàn)的可能性。 接下來就是寫出狀態(tài)轉(zhuǎn)移方程了，一旦狀態(tài)轉(zhuǎn)移方程寫出，那么 f[i,j]就可以由 f[x,y]等其他狀態(tài)得來，因?yàn)榈玫阶詈笪覀円蟮?f[n,k]。通過類推，小狀態(tài)可以分成更小的狀態(tài)。 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[i j,j]。 最后加點(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)。 要求輸出； （ 1） tree的最高加分 （ 2） tree的前序遍歷 【輸入格式】 第 1行：一個(gè)整數(shù) n（ n＜ 30）， 為節(jié)點(diǎn)個(gè)數(shù)。 這樣，我們只要枚舉 i~j這個(gè)區(qū)間和枚舉這個(gè)區(qū)間的根 k就可以了。動(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]。 因?yàn)榇祟}給我們的是中序遍歷，所以如果 a[i]為根，那么 a[1]~a[i1]就是這棵樹的左子樹， a[i+1]~a[n]就是這棵樹的右子樹。不考慮它的空 子樹。 ∴ f[i,j]:=f[ij,1]+f[ij,2]…+f[i j,j1]+f[ij,j] =f[i1,j1]+f[ij,j]。雖然可以輕松過這題，但如果 n=50000， k=200，這樣的方法就超時(shí)了。 f[i,j]:=f[ij,1]+f[ij,2]+f[ij,3]+…+f[i j,j1]+f[ij,j]。乍一看我們沒發(fā)現(xiàn)什么規(guī)律，但是這些分割方法都有一個(gè)共同點(diǎn)： 因?yàn)椴辉试S出 現(xiàn) 10=0+10這 種分割，所以 有了這個(gè)性質(zhì)，我們來嘗試下面的操作：將所有小整數(shù)都減去 1。此類問題一般要用到數(shù)學(xué)公式、數(shù)學(xué)證明、方程變形、極端化等思想，根據(jù)題目的不同適當(dāng)選取方法。 【 輸入 】 n， k (6n=200， 2=k=6) 【 輸出 】 一個(gè)整數(shù)，即不同的分法。 1， 1， 5。這樣，最大的復(fù)雜度就是 t(t1)*（石頭個(gè)數(shù) +1） =90*101=9090，比之前的復(fù)雜度大大降低。所以，只有當(dāng) t=s+1時(shí)，連續(xù)的點(diǎn)的起始位置才能盡量后面。如果 s=4， t=5，在一段 100000的距離中沒有石頭，其實(shí) 12以后的點(diǎn)都是不用遞推就知道肯定能到達(dá)的。 我們可以發(fā)現(xiàn)題目的一個(gè)玄機(jī)：雖然 L很大，但是M卻很小，也就是說： 石子稀疏對(duì)我們解題有什么幫助呢？我們來看一下下面的推斷： 第一種情況： 當(dāng) s=t時(shí)，很簡(jiǎn)單，青蛙踩到的石頭肯定是 s的倍數(shù)，那么只要統(tǒng)計(jì)一下所有石子中有多少是 s的倍數(shù)，輸出即可。 但是有個(gè)地方我們忽略了，那就是數(shù)據(jù)規(guī)模。所有相鄰的整數(shù)之間用一個(gè)空格隔開。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。 過河（ NOIp2022） 【 問題描述 】 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。 【 限制 】 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ù)的一段，每次加入頭或尾。 m次后取完矩陣所有元素； 2. 每次取走的各個(gè)元素只能是該元素所在行的行首或行尾； 3. 每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分 = 被取走的元素值 *2i，其中 i表示第 i次取數(shù)（從 1開始編號(hào)）； 4. 游戲結(jié)束總得分為 m次取數(shù)得分之和。明顯第 1~3之間有 1個(gè)單詞，而 1~4之間呢？ 1~3有的它肯定也有，再去枚舉單詞中有沒有是 cabc后綴的單詞。所以第一步刪串。要求輸出最大的個(gè)數(shù)。要求將此字母串分 成 k份 (1k=40)，且每份中包含的單詞個(gè)數(shù)加起來總數(shù)最大 (每份中包含的單詞可以部分重疊。 對(duì)于題目中所說的具有很強(qiáng)枚舉意味的變量（如 k段， n次等），一般將其放入狀態(tài)中枚舉。 【 輸出 】 輸出所求得的最大乘積（一個(gè)自然數(shù)）。則第 1兩顆珠子聚合后釋放的能量為(4⊕ 1)=10*2*3=60。 需要時(shí)， Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。 End。 (i=kj) f[i,j]:=Min(f[i,k],f[k+1,j]}+ 而 f[i,i]和一段石子的總和是可以預(yù)處理的，只要將石子序列倍長(zhǎng)，復(fù)雜度 O(n^3)，此題就能順利 AC了。 因?yàn)轭}目中說，只能歸并相鄰的兩堆石子。 【 輸入數(shù)據(jù) 】 第一行為石子堆數(shù) N。 還有一件事情需要注意，全班每個(gè)同學(xué)愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時(shí)用 0表示），可以用一個(gè) 0100的自然數(shù)來表示，數(shù)越大表示越好心。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。 傳紙條（
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1