動(dòng)態(tài)規(guī)劃基礎(chǔ)和建模

動(dòng)態(tài)規(guī)劃基礎(chǔ)和建模第1頁，共105頁，2023年，2月20日，星期一動(dòng)態(tài)規(guī)劃是統(tǒng)籌學(xué)的重要內(nèi)容動(dòng)態(tài)規(guī)劃是OI的重要內(nèi)容據(jù)不完全統(tǒng)計(jì)，每次考試動(dòng)態(tài)規(guī)劃起碼有一道題前言動(dòng)態(tài)規(guī)劃很重要！第2頁，共105頁，2023年，2月20日，星期一這個(gè)課件的目的：對動(dòng)態(tài)規(guī)劃的模型進(jìn)行了一些總結(jié)有部分內(nèi)容超出了NOIP范圍為同學(xué)們提供一個(gè)刷題的方向請同學(xué)們踴躍發(fā)言前言第3頁，共105頁，2023年，2月20日，星期一階段狀態(tài)決策狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移方程動(dòng)態(tài)規(guī)劃的基本概念第4頁，共105頁，2023年，2月20日，星期一最優(yōu)子結(jié)構(gòu)無后效性原則重疊子問題動(dòng)態(tài)規(guī)劃的基本概念DP是一種記憶化的思想第5頁，共105頁，2023年，2月20日，星期一拓展一下：階段->拓?fù)湫驙顟B(tài)->點(diǎn)狀態(tài)轉(zhuǎn)移->邊決策->前驅(qū)？DFA？動(dòng)態(tài)規(guī)劃的基本概念DP是狀態(tài)空間上的最短（長）路或者可行路第6頁，共105頁，2023年，2月20日，星期一實(shí)現(xiàn)方式：遞推：順推和逆推記憶化搜索前者靈活，優(yōu)化方法多后者可以減少不必要節(jié)點(diǎn)的計(jì)算動(dòng)態(tài)規(guī)劃的基本概念第7頁，共105頁，2023年，2月20日，星期一時(shí)間復(fù)雜度：狀態(tài)數(shù)*轉(zhuǎn)移費(fèi)用動(dòng)態(tài)規(guī)劃的基本概念第8頁，共105頁，2023年，2月20日，星期一線性模型區(qū)間模型矩形模型樹形模型背包模型圖狀模型SCDP多線程DP多重DP更廣泛的動(dòng)態(tài)規(guī)劃的模型第9頁，共105頁，2023年，2月20日，星期一單線問題：上樓梯問題LIS問題烏龜棋詩人小G（簡化版）雙線問題：LCS問題模糊匹配線性模型第10頁，共105頁，2023年，2月20日，星期一Zbwmqlw神犇要上樓梯，他一次可以上一層，也可以上兩層。樓梯有n層有多少種上樓梯的方案上樓梯問題第11頁，共105頁，2023年，2月20日，星期一N<=10^7？設(shè)f[i]表示到第i層得方案數(shù)前一步可以上一層也可以上兩層F[i]=f[i-1]+f[i-2]N<=10^15？矩陣乘法上樓梯問題第12頁，共105頁，2023年，2月20日，星期一給定一個(gè)數(shù)列{an}，求它的一個(gè)子序列{bm}滿足b1<b2<b3<…<bm使得m最大N<=10000LIS問題第13頁，共105頁，2023年，2月20日，星期一設(shè)f[i]表示以i結(jié)尾的LIS的長度F[i]=max{f[j]}+1,j<i且a[j]<a[i]時(shí)間復(fù)雜度？O(n^2)如何優(yōu)化？LIS問題第14頁，共105頁，2023年，2月20日，星期一對于i來說，如果存在一個(gè)長度為len的LIS以i結(jié)尾，那么也一定存在長度<len的即：滿足單調(diào)性！設(shè)g[i]表示f[j]=i的最小的a[j]二分g[k]>=a[i]的最大的kF[i]=k+1時(shí)間復(fù)雜度O(nlogn)LIS問題第15頁，共105頁，2023年，2月20日，星期一烏龜棋（NOIP2010t）第16頁，共105頁，2023年，2月20日，星期一F[i][a][b][c][d]表示到位置i，四種操作分別進(jìn)行了a,b,c,d次決策有四種時(shí)間復(fù)雜度：O(nc^4)TLE+MLE烏龜棋第17頁，共105頁，2023年，2月20日，星期一烏龜棋第18頁，共105頁，2023年，2月20日，星期一一首詩包含了若干個(gè)句子，對于一些連續(xù)的短句，可以將它們用空格隔開并放在一行中，注意一行中可以放的句子數(shù)目是沒有限制的。小G給每首詩定義了一個(gè)行標(biāo)準(zhǔn)長度（行的長度為一行中符號(hào)的總個(gè)數(shù)），他希望排版后每行的長度都和行標(biāo)準(zhǔn)長度相差不遠(yuǎn)。顯然排版時(shí)，不應(yīng)改變原有的句子順序，并且小G不允許把一個(gè)句子分在兩行或者更多的行內(nèi)。在滿足上面兩個(gè)條件的情況下，小G對于排版中的每行定義了一個(gè)不協(xié)調(diào)度,為這行的實(shí)際長度與行標(biāo)準(zhǔn)長度差值絕對值的P次方，而一個(gè)排版的不協(xié)調(diào)度為所有行不協(xié)調(diào)度的總和。小G最近又作了幾首詩，現(xiàn)在請你對這首詩進(jìn)行排版，使得排版后的詩盡量協(xié)調(diào)（即不協(xié)調(diào)度盡量?。?，并把排版的結(jié)果告訴他。詩人小G（NOI2009）簡化版第19頁，共105頁，2023年，2月20日，星期一F[i]表示前i句詩的最小不協(xié)調(diào)度F[i]=min{f[j]+(sum[i]-sum[j]+i-j-L)^p}時(shí)間復(fù)雜度O(n^2)優(yōu)化？導(dǎo)數(shù)證明四邊形不等式，有興趣的同學(xué)自己查閱有關(guān)資料詩人小G第20頁，共105頁，2023年，2月20日，星期一給定兩個(gè)字符串s，t求最長公共字串例：abcde和ace的LCS是aceN<=1000LCS問題第21頁，共105頁，2023年，2月20日，星期一設(shè)f[i][j]表示第一個(gè)串到i，第二個(gè)串到j(luò)的LCSF[i][j]=f[i-1][j-1]+1,s[i]=t[j]=min{f[i-1][j],f[i][j-1]},s[i]!=t[j]時(shí)間復(fù)雜度O(n^2)LCS問題第22頁，共105頁，2023年，2月20日，星期一給定兩個(gè)字符串s和t，每個(gè)字符串有英文字母和*？！組成，*？！的含義分別是：*：匹配一個(gè)或多個(gè)字符；？：匹配至少一個(gè)至多三個(gè)字符；?。浩ヅ渲辽偃齻€(gè)字符。問兩個(gè)字符串是否能夠匹配。N<=1000模糊匹配（POJ1229）第23頁，共105頁，2023年，2月20日，星期一模糊匹配第24頁，共105頁，2023年，2月20日，星期一石子歸并回文詞決斗問題Blocks區(qū)間模型第25頁，共105頁，2023年，2月20日，星期一有n堆石子，第i堆重a[i]每次可以合并相鄰兩堆合并費(fèi)用為新堆的重量求合并成一堆的最小費(fèi)用N<=200石子歸并第26頁，共105頁，2023年，2月20日，星期一合并的費(fèi)用是一段的和設(shè)f[i][j]表示合并i到j(luò)的一段F[i][j]=min{f[i][k]+f[k+1][j]}+sum[i][j]時(shí)間復(fù)雜度O(n^3)石子歸并第27頁，共105頁，2023年，2月20日，星期一給定一個(gè)字符串s，要求添加最少的字符，使得s成為一個(gè)回文串。N<=5000回文詞（IOI2000）第28頁，共105頁，2023年，2月20日，星期一abcba：回文abcbc：不回文F[i][j]表示i到j(luò)變成回文的最小代價(jià)F[i][j]=f[i+1][j-1],s[i]=s[j]=min{f[i+1][j],f[i][j-1]}+1,s[i]!=s[j]時(shí)間復(fù)雜度O(n^2)回文詞第29頁，共105頁，2023年，2月20日，星期一N個(gè)人排成一圈，他們要決斗N-1場，其中相鄰的兩人決斗（即第i個(gè)人與第i+1個(gè)人決斗，第N個(gè)人與第1個(gè)人決斗），死者退出，最終剩下的人勝利。將任意兩個(gè)人之間決斗的輸贏情況告訴你，決斗順序由你安排，問哪些人可能成為最終的勝利者？N<=200決斗問題（POI99）第30頁，共105頁，2023年，2月20日，星期一首先把環(huán)復(fù)制一份接到后面然后一個(gè)人獲勝就是跟自己相遇Meet[i][j]表示i能j相遇Meet[i][j]=meet[i][k]&&meet[k][j]&&(beat[i][k]||beat[j][k])時(shí)間復(fù)雜度O(n^3)決斗問題第31頁，共105頁，2023年，2月20日，星期一Blocks（POJ1390）第32頁，共105頁，2023年，2月20日，星期一我們可以選擇保留一部分不消除，而跟前面相同顏色的合并起來一起消除以獲得更大的費(fèi)用，所以再設(shè)計(jì)狀態(tài)時(shí)，我們需要把后面留下的一起考慮進(jìn)去。首先我們把相鄰的相同顏色的縮成一段，len[i]表示第i段的長度記pre[i]表示第i段往前第一個(gè)與i顏色相同的段的編號(hào)Blocks第33頁，共105頁，2023年，2月20日，星期一設(shè)f[i][j][k]表示把從第i段到第j段，最后面有長度為k的與j顏色相同的消去的最大得分F[i][j][k]=max{f[i][j-1][0]+(len[j]+k)^2,f[i][pre[j]][len[j]+k]+f[pre[j]+1][j][0]}記憶化搜索實(shí)現(xiàn)效率高Blocks第34頁，共105頁，2023年，2月20日，星期一降維拆成鏈：滑雪子矩形：采油區(qū)域行列：棋盤分割對角線：轉(zhuǎn)紙條矩形模型第35頁，共105頁，2023年，2月20日，星期一Michael喜歡滑雪這并不奇怪，因?yàn)榛┑拇_很刺激。可是為了獲得速度，滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降機(jī)來載你。Michael想知道載一個(gè)區(qū)域中最長的滑坡。區(qū)域由一個(gè)二維數(shù)組給出。數(shù)組的每個(gè)數(shù)字代表點(diǎn)的高度?；⊿HTSC2002）第36頁，共105頁，2023年，2月20日，星期一滑雪第37頁，共105頁，2023年，2月20日，星期一采油區(qū)域（APIO2009）第38頁，共105頁，2023年，2月20日，星期一一共只有六種情況：采油區(qū)域第39頁，共105頁，2023年，2月20日，星期一采油區(qū)域第40頁，共105頁，2023年，2月20日，星期一采油區(qū)域第41頁，共105頁，2023年，2月20日，星期一采油區(qū)域第42頁，共105頁，2023年，2月20日，星期一將一個(gè)８*８的棋盤進(jìn)行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了n-1次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。（每次切割都只能沿著棋盤格子的邊進(jìn)行。）棋盤分割（NOI99）第43頁，共105頁，2023年，2月20日，星期一棋盤分割第44頁，共105頁，2023年，2月20日，星期一棋盤分割第45頁，共105頁，2023年，2月20日，星期一棋盤分割第46頁，共105頁，2023年，2月20日，星期一傳紙條（NOIP2008T）第47頁，共105頁，2023年，2月20日，星期一傳紙條第48頁，共105頁，2023年，2月20日，星期一傳紙條第49頁，共105頁，2023年，2月20日，星期一數(shù)值分配型：選課，貪吃的九頭龍多叉轉(zhuǎn)二叉樹形背包位置轉(zhuǎn)移型：CellPhoneNetwork鏈劃分型：樹的最長鏈可轉(zhuǎn)化成區(qū)間模型和線性模型：加分二叉樹樹形模型第50頁，共105頁，2023年，2月20日，星期一在大學(xué)里每個(gè)學(xué)生，為了達(dá)到一定的學(xué)分，必須從很多課程里選擇一些課程來學(xué)習(xí)，在課程里有些課程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之前學(xué)習(xí)。現(xiàn)在有N門功課，每門課有個(gè)學(xué)分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學(xué)完了課程a，才能學(xué)習(xí)課程b）。一個(gè)學(xué)生要從這些課程里選擇M門課程學(xué)習(xí)，問他能獲得的最大學(xué)分是多少？選課（CTSC99）第51頁，共105頁，2023年，2月20日，星期一如果要選課程a必須要選課程b，那么就在a和b之間連邊，這樣，得到的會(huì)是一個(gè)森林。于是我們添加一個(gè)節(jié)點(diǎn)0，學(xué)分為0，把這個(gè)森林連成樹，于是問題就是從一顆n+1個(gè)節(jié)點(diǎn)的樹里選m+1個(gè)節(jié)點(diǎn)，使得總分最大。這樣，點(diǎn)0是必須選的。選課第52頁，共105頁，2023年，2月20日，星期一選課第53頁，共105頁，2023年，2月20日，星期一傳說中的九頭龍是一種特別貪吃的動(dòng)物。雖然名字叫“九頭龍”，但這只是說它出生的時(shí)候有九個(gè)頭，而在成長的過程中，它有時(shí)會(huì)長出很多的新頭，頭的總數(shù)會(huì)遠(yuǎn)大于九，當(dāng)然也會(huì)有舊頭因衰老而自己脫落。有一天，有M個(gè)腦袋的九頭龍看到一棵長有N個(gè)果子的果樹，喜出望外，恨不得一口把它全部吃掉。可是必須照顧到每個(gè)頭，因此它需要把N個(gè)果子分成M組，每組至少有一個(gè)果子，讓每個(gè)頭吃一組。貪吃的九頭龍（NOI2002）第54頁，共105頁，2023年，2月20日，星期一這M個(gè)腦袋中有一個(gè)最大，稱為“大頭”，是眾頭之首，它要吃掉恰好K個(gè)果子，而且K個(gè)果子中理所當(dāng)然地應(yīng)該包括唯一的一個(gè)最大的果子。果子由N-1根樹枝連接起來，由于果樹是一個(gè)整體，因此可以從任意一個(gè)果子出發(fā)沿著樹枝“走到”任何一個(gè)其他的果子。貪吃的九頭龍第55頁，共105頁，2023年，2月20日，星期一對于每段樹枝，如果它所連接的兩個(gè)果子需要由不同的頭來吃掉，那么兩個(gè)頭會(huì)共同把樹枝弄斷而把果子分開；如果這兩個(gè)果子是由同一個(gè)頭來吃掉，那么這個(gè)頭會(huì)懶得把它弄斷而直接把果子連同樹枝一起吃掉。當(dāng)然，吃樹枝并不是很舒服的，因此每段樹枝都有一個(gè)吃下去的“難受值”，而九頭龍的難受值就是所有頭吃掉的樹枝的“難受值”之和。九頭龍希望它的“難受值”盡量小，你能幫它算算嗎？貪吃的九頭龍第56頁，共105頁，2023年，2月20日，星期一貪吃的九頭龍第57頁，共105頁，2023年，2月20日，星期一貪吃的九頭龍第58頁，共105頁，2023年，2月20日，星期一我們從多叉轉(zhuǎn)二叉的角度來看這道題貪吃的九頭龍第59頁，共105頁，2023年，2月20日，星期一給定一棵樹，求樹的最長鏈樹的最長鏈第60頁，共105頁，2023年，2月20日，星期一貪心做法：兩次BFS證明樹的最長鏈第61頁，共105頁，2023年，2月20日，星期一動(dòng)態(tài)規(guī)劃：設(shè)f[i]表示兒子連上來的最長鏈，g[i]表示兒子連上來的次長鏈，h[i]表示父親來的最長鏈F[i]=max{f[j]}+1同時(shí)更新g[i]H[i]=max{f[p],h[p]}+1,f[p]>f[i]+1=max{g[p],h[p]}+1,f[p]=f[i]+1樹的最長鏈第62頁，共105頁，2023年，2月20日，星期一給定一棵樹，求樹的最小點(diǎn)支配集。N<=10000支配集：點(diǎn)覆蓋點(diǎn)CellPhoneNetwork（POJ3659）第63頁，共105頁，2023年，2月20日，星期一CellPhoneNetwork第64頁，共105頁，2023年，2月20日，星期一CellPhoneNetwork第65頁，共105頁，2023年，2月20日，星期一CellPhoneNetwork第66頁，共105頁，2023年，2月20日，星期一

設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第j個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子樹都有一個(gè)加分，任一棵子樹subtree（也包含tree本身）的加分計(jì)算方法如下：subtree的左子樹的加分×subtree的右子樹的加分＋subtree的根的分?jǐn)?shù)

若某個(gè)子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。

試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；

（1）tree的最高加分

（2）tree的前序遍歷加分二叉樹（NOIP2003）第67頁，共105頁，2023年，2月20日，星期一加分二叉樹第68頁，共105頁，2023年，2月20日，星期一部分背包01背包完全背包多重背包分組背包依賴背包泛化物品背包模型第69頁，共105頁，2023年，2月20日，星期一給定一個(gè)容量為m的背包和n個(gè)物品，每個(gè)物品有一個(gè)價(jià)值v和一個(gè)費(fèi)用w，求在滿足容量限制的情況下最大化價(jià)值。NPC問題背包問題第70頁，共105頁，2023年，2月20日，星期一特點(diǎn)：物品可以任意劃分方法：求單位價(jià)值，貪心部分背包問題第71頁，共105頁，2023年，2月20日，星期一01背包問題第72頁，共105頁，2023年，2月20日，星期一空間優(yōu)化：滾動(dòng)數(shù)組代碼：voidZeroOnePack{for(inti=1;i<=n;i++)for(intj=m;j>=cost[i];j--)gmax(f[j],f[j-cost[i]]+value[i]);}01背包問題第73頁，共105頁，2023年，2月20日，星期一完全背包問題第74頁，共105頁，2023年，2月20日，星期一特點(diǎn)：每類問題有個(gè)數(shù)限制c[i]基本想法：每類物品的每一個(gè)看作一個(gè)物品，轉(zhuǎn)化成01背包代碼：voidLimitedPack{for(inti=1;i<=n;i++)for(intj=1;j<=limit[i];j++)for(intk=m;k>=cost[i];k--)gmax(f[k],f[k-cost[i]]+value[i]);}多重背包問題第75頁，共105頁，2023年，2月20日，星期一優(yōu)化：二進(jìn)制拆分原理：2^k能夠表示出0~2^(k+1)-1的所有數(shù)把c[i]拆成若干2^k相加O(nmlogc)多重背包問題第76頁，共105頁，2023年，2月20日，星期一特點(diǎn)：物品被分為很多組，每組之間有限制。假設(shè)限制為：每組只能取一個(gè)F[i][j]=max{f[i-1][j],f[i-1][j-w[i][k]]+v[i][k]}代碼：voidGroupPack{for(inti=1;i<=n;i++)for(intj=m;j>=mincost[i];j--)for(intk=1;k<=cnt[i];k++)if(cost[i][k]<=j)gmax(f[j],f[j-cost[i][k]]+value[i][k];}分組背包問題第77頁，共105頁，2023年，2月20日，星期一考試的時(shí)候合理分配時(shí)間是很重要的，我們應(yīng)該在同樣的時(shí)間內(nèi)盡量得到更多的分?jǐn)?shù)。現(xiàn)在有m道題需要在n分鐘內(nèi)解決，每道題分為p個(gè)步驟，每道題的每個(gè)步驟都會(huì)有不同的分值，所需時(shí)間也不盡相同?，F(xiàn)在你可以從任意一道題的任意一個(gè)步驟開始，如果當(dāng)前步驟與上一步驟不連續(xù)，則需要q分鐘的思考時(shí)間（每題第一個(gè)步驟之前同樣需要思考），請確定自己的策略使得獲得的分?jǐn)?shù)最高。分配時(shí)間（WFTSC2009T）第78頁，共105頁，2023年，2月20日，星期一每道題實(shí)際上是一個(gè)組。我們可以發(fā)現(xiàn)，每個(gè)步驟選或不選對后面的決策是有影響的，所以我們考慮加一維來區(qū)分。設(shè)f[i][j][k]表示前i道題的前j個(gè)步驟，其中第i道題的第j個(gè)步驟被選，在k分鐘內(nèi)解決的最大得分，g[i][j][k]表示前i道題的前j個(gè)步驟，其中第i道題的第j個(gè)步驟不被選，在k分鐘內(nèi)解決的最大得分，那么：分配時(shí)間第79頁，共105頁，2023年，2月20日，星期一分配時(shí)間第80頁，共105頁，2023年，2月20日，星期一

依賴背包問題，顧名思義，就是一些物品可以選要建立在其它一些物品被選的基礎(chǔ)之上。這類問題往往是建立在樹上的，所以通常也叫樹形背包問題。鑒于在樹形模型中已經(jīng)有了比較詳細(xì)的討論，這里不再詳細(xì)展開依賴背包問題第81頁，共105頁，2023年，2月20日，星期一泛化物品第82頁，共105頁，2023年，2月20日，星期一voidGeneralMatters{for(inti=1;i<=n;i++)for(intj=m;j>=0;j--)for(intk=0;k<=j;k++)gmax(f[j],f[j-k]+cost(i,k));}泛化物品第83頁，共105頁，2023年，2月20日，星期一回顧上面的數(shù)值分配型的樹形動(dòng)態(tài)規(guī)劃，考慮其中的一個(gè)節(jié)點(diǎn)i，其子樹就相當(dāng)于一個(gè)一個(gè)的泛化物品，隨著分配給它們的數(shù)值的變化，其價(jià)值也在不斷的變化。由此可見，泛化物品在各個(gè)方面都有著很廣泛的應(yīng)用。泛化物品第84頁，共105頁，2023年，2月20日，星期一環(huán)狀：Naptime拓?fù)鋱D：關(guān)鍵路徑一般圖模型最優(yōu)貿(mào)易圖狀模型第85頁，共105頁，2023年，2月20日，星期一找一個(gè)位置把環(huán)拆成鏈DP把鏈的首尾接成環(huán)枚舉首狀態(tài)環(huán)狀模型第86頁，共105頁，2023年，2月20日，星期一小F同學(xué)最近特別累，老是想睡覺小F同學(xué)把一天分為n個(gè)時(shí)段，選擇不一定連續(xù)的m個(gè)時(shí)段來睡覺小F同學(xué)睡眠質(zhì)量不好，每次睡覺要花1個(gè)時(shí)段來進(jìn)入睡眠每個(gè)時(shí)段有一個(gè)休息值a[i]，如果小F同學(xué)選擇在[I,j]的時(shí)段內(nèi)睡覺的話，得到的休息就是a[i+1]+…+a[j]，因?yàn)闀r(shí)段i被用來進(jìn)入睡眠了如何選擇能夠休息的最好？注意天與天是連續(xù)的，即這n個(gè)時(shí)段是一個(gè)環(huán)Naptime（POJ2228）第87頁，共105頁，2023年，2月20日，星期一因?yàn)榄h(huán)首尾相接的地方會(huì)對結(jié)果產(chǎn)生影響，所以要枚舉開始的狀態(tài)，做幾遍DP設(shè)f[i][j][0]表示前i個(gè)時(shí)間段睡了j段，第i段不睡的最長時(shí)間，f[i][j][1]表示第i段睡的最長時(shí)間，那么：f[i][j][0]=max{f[i-1][j][0],f[i-1][j][1]}f[i][j][1]=max{f[i-1][j-1][0],f[i-1][j-1][1]+t[i]}初始時(shí)，所有的f=-INF然后枚舉第一個(gè)時(shí)間段睡不睡，分別使f[1][1][1]=1,f[1][0][0]=1，做兩次DP內(nèi)存限制比較緊，要滾動(dòng)naptime第88頁，共105頁，2023年，2月20日，星期一邊拓?fù)渑判蜻匘PSCC縮點(diǎn)拓?fù)鋱D模型第89頁，共105頁，2023年，2月20日，星期一給定一個(gè)DAG，求從s到t的最長路關(guān)鍵路徑第90頁，共105頁，2023年，2月20日，星期一設(shè)f[i]表示從s到i的最長路徑F[i]+dis[i][j]->f[j]拓?fù)渑判虻倪^程中解決關(guān)鍵路徑第91頁，共105頁，2023年，2月20日，星期一給定一個(gè)圖，邊有的是單向的，有的是雙向的有一個(gè)水晶球，每個(gè)點(diǎn)有一個(gè)價(jià)格從s出發(fā)到t，沿途在某個(gè)點(diǎn)買入水晶球，在另一個(gè)點(diǎn)賣出顯然你要先買入才能賣出最大化收益最優(yōu)貿(mào)易（NOIP2009T）第92頁，共105頁，2023年，2月20日，星期一方法一：同一個(gè)SCC里的點(diǎn)都可以走到，可以在其中任意一個(gè)買，任意一個(gè)賣收縮SCC，記錄SCC的最大值和最小值F[i]表示到i的最大獲利，g[i]表示到i的最小價(jià)格，minv[i]表示i所在SCC的最小價(jià)格，maxv[i]表示i所在SCC的最大價(jià)格G[i]=min{g[j],minv[i]}F[i]=max{f[j],maxv[i]-g[i]}邊拓?fù)渑判蜻呑鲎顑?yōu)貿(mào)易第93頁，共105頁，2023年，2月20日，星期一方法二：F[i][0]表示到i點(diǎn)，沒有水晶球的最大F[i][1]表示到i點(diǎn)，有水晶球的最大F[i][0]=max{f[j][0],f[j][1]+w[i]}f[i][1]=max{f[j][1],-w[i]}前面說過：動(dòng)態(tài)規(guī)劃是狀態(tài)圖的最短路或最長路嵌套在SPFA算法中，迭代求解最優(yōu)貿(mào)易第94頁，共105頁，2023年，2月20日，星期一這類問題在NOIP中一般不會(huì)出現(xiàn)，但鑒于在NOIP的模擬題和WFTSC中出現(xiàn)了不止一次，稍微提一下插頭DP棋盤DP集合DP狀態(tài)壓縮模型第95頁，共105頁，2023年，2月20日，星期一把問題的狀態(tài)壓縮成一個(gè)k進(jìn)制數(shù)來表示，利用這個(gè)數(shù)的每一位反映出來的信息來進(jìn)行轉(zhuǎn)移問題規(guī)模往往特別小狀態(tài)壓縮模型第96頁，共105頁，2023年，2月20日，星期一困惑的旅行家（WFTSC2010T）第97頁，共105頁，2023年，2月20日，星期一經(jīng)典的TSP問題最優(yōu)哈密頓回路設(shè)f[i][S]表示當(dāng)前在i點(diǎn)，經(jīng)過的點(diǎn)的集合是SF[i][S]=min{f[j][S-{i}]+dis[j][i]}Ans=min{f[i][2^n-1]+dis[i][1]}困惑的旅行家第98頁，共105頁，2023年，2月20日，星期一