DP  基礎(chǔ)的基礎(chǔ)

一個(gè)例題：

>填滿網(wǎng)格

?          給出一個(gè)2*n的網(wǎng)格，你現(xiàn)在需要用n個(gè) 2*1的多米諾骨牌占滿整個(gè)棋盤(pán)。

?          多米諾骨牌可以橫著或者豎著放。

?          求有多少方案數(shù)占滿整個(gè)棋盤(pán)。

?          N<=10^6

>SOLUTION

?          設(shè)f[n]為n列的答案

?          則根據(jù)如何對(duì)最后一兩列放多米諾分情況討論可得

?          f[n]=f[n-1] f[n-2]。

?         

?          這是遞推，也算是一個(gè)簡(jiǎn)單的dp，只不過(guò)絕大多數(shù)dp的轉(zhuǎn)移方程不是根據(jù)這題一樣簡(jiǎn)簡(jiǎn)單單的一個(gè)加號(hào)就解決的。

>網(wǎng)格圖路徑計(jì)數(shù)

?          給出一個(gè)n*m的網(wǎng)格，每次只能向右或者向下走，求從(1,1)走到(n,m)的方案數(shù)，其中有些位置是不能走的。

?         

?          n,m<=1000

>Solution

?          如果沒(méi)有障礙物：設(shè)dp[i][j]表示從(1,1)，走到(i,j)的方案數(shù)。

?          考慮上一步從哪里走過(guò)來(lái)可得，dp[i][j]=dp[i-1][j] dp[i][j-1]。

?          答案就是dp[n][m]。

?          對(duì)于障礙：如果(i,j)是一個(gè)障礙，則定義dp[i][j]=0。

>走金字塔的最大價(jià)值路徑

?          給出一個(gè)高度為n的金字塔，你現(xiàn)在要從金字塔的頂端走到金字塔的底端。

?          金字塔的第i層，第j房間（記為(i,j) ）有價(jià)值為a[i][j]的寶藏，每一步能從(i,j)能走到，(i 1,j) , (i 1,j 1)。求從金字塔頂部走到底部能獲得的最大的價(jià)值是多少？

?          n=4的一個(gè)例子。

?          7

?          3 8

?          8 1 0

?          2 7 4 4

?          ans=7 3 8 7=25

>Solution

?          和前面兩題差不多。只不過(guò)前面是求方案數(shù)，運(yùn)算法則為加法，而這里求最優(yōu)值，運(yùn)算法則是取max。

?          設(shè)dp[i][j]表示從塔頂走到(i,j)能得到的最大的價(jià)值是多少。

?          則dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]) a[i][j]。

DP基礎(chǔ)

>動(dòng)態(tài)規(guī)劃的基本思想？

?          利用最優(yōu)化原理把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解。

?          更具體的，假設(shè)我們可以計(jì)算出小問(wèn)題的最優(yōu)解，那么我們憑借此可以推出大問(wèn)題的最優(yōu)解，進(jìn)而我們又可以推出更大問(wèn)題的最優(yōu)解。（要滿足最優(yōu)子結(jié)構(gòu)）

?          （從小問(wèn)題答案推到大問(wèn)題的答案）

?          而最小的問(wèn)題也就是邊界情況我們可以直接計(jì)算出答案來(lái)。

?          基本思想是將待求解的問(wèn)題劃歸為若干個(gè)子問(wèn)題（階段），按順序求解子階段，小的子問(wèn)題的解，為更大子問(wèn)題的求解提供了有用的信息。

?          由于動(dòng)態(tài)規(guī)劃解決的問(wèn)題多數(shù)有重疊子問(wèn)題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對(duì)每一個(gè)子問(wèn)題只解一次。

>動(dòng)態(tài)規(guī)劃的狀態(tài)

• 動(dòng)態(tài)規(guī)劃過(guò)程中，需要有狀態(tài)表示和最優(yōu)化值（方案值）。

• 狀態(tài)表示：是對(duì)當(dāng)前子問(wèn)題的解的局面集合的一種（充分的）描述。

• 最優(yōu)化值：則是對(duì)應(yīng)的狀態(tài)集合下的最優(yōu)化信息（方案值），我們最終能通過(guò)其直接或間接得到答案。

>狀態(tài)表示

?          對(duì)于狀態(tài)的表示，要滿足三條性質(zhì)

?          1：具有最優(yōu)化子結(jié)構(gòu)：即問(wèn)題的最優(yōu)解能有效地從問(wèn)題的子問(wèn)題的最優(yōu)解構(gòu)造而來(lái)。

?          2：能夠全面的描述一個(gè)局面。一個(gè)局面有一個(gè)答案，而這個(gè)局面是需要一些參數(shù)來(lái)描述的。

?          3：同時(shí)具有簡(jiǎn)潔性：盡可能的簡(jiǎn)化狀態(tài)的表示，以獲得更優(yōu)的時(shí)間復(fù)雜度。

設(shè)計(jì)狀態(tài)的關(guān)鍵就是 充分描述，盡量簡(jiǎn)潔。

>動(dòng)態(tài)規(guī)劃的精髓？——狀態(tài)轉(zhuǎn)移

• 由于具有最優(yōu)化子結(jié)構(gòu)（在最優(yōu)化問(wèn)題中），所以求當(dāng)前狀態(tài)的最優(yōu)值可以通過(guò)其他的（較小的問(wèn)題）狀態(tài)的最優(yōu)值加以變化而求出。所以，當(dāng)一個(gè)狀態(tài)的所有子結(jié)構(gòu)都已經(jīng)被計(jì)算之后，我們就可以通過(guò)一個(gè)過(guò)程計(jì)算出他的最優(yōu)值。這個(gè)過(guò)程就是狀態(tài)的轉(zhuǎn)移。

• 注意：狀態(tài)的轉(zhuǎn)移需要滿足要考慮到所有可能性。

>怎么計(jì)算動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度？

?          一般簡(jiǎn)單動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度==狀態(tài)數(shù)×狀態(tài)轉(zhuǎn)移復(fù)雜度。

?          同時(shí)也就引出了dp的兩種優(yōu)化時(shí)間的方法

?          1：減少狀態(tài)的維數(shù)。

?          2：加速狀態(tài)轉(zhuǎn)移，例如數(shù)據(jù)結(jié)構(gòu)優(yōu)化或者分析性質(zhì)。

----------下面看題-----------

>最長(zhǎng)上升子序列

• 給出一個(gè)長(zhǎng)度為n的數(shù)列 a[1..n], 求這個(gè)數(shù)列的最長(zhǎng)上升子序列。

• 就是給你一個(gè)序列，請(qǐng)你在其中求出一段不斷嚴(yán)格上升的子序列，子序列是不一定要求連續(xù)的。

• 2,3,4,7和2,3,4,6是序列2 5 3 4 1 7 6的兩種選取方案。最長(zhǎng)上升子序列的長(zhǎng)度就是4。

• N<=1000

>Solution

?          這是一道最為經(jīng)典的完全用動(dòng)態(tài)規(guī)劃來(lái)解決的問(wèn)題。

?          設(shè)dp[i]為以a[i]為末尾的最長(zhǎng)上升子序列的長(zhǎng)度。

?          最后的答案就是我枚舉一下最長(zhǎng)上升子序列的結(jié)束位置，然后取一個(gè)dp[i]最大值即可。

?          問(wèn)題是如何求這個(gè)數(shù)組？

?          那我們回過(guò)頭來(lái)想一想最開(kāi)始說(shuō)的動(dòng)態(tài)規(guī)劃的基本思想，從小的問(wèn)題推出大的問(wèn)題。

?          假設(shè)我們知道了dp[1..(i-1)]，我們?cè)趺床拍芨鶕?jù)這些信息推出來(lái)dp[i]。

?          再次強(qiáng)化一下定義：dp[i]表示以i結(jié)尾的最長(zhǎng)上升子序列。

?          我們只需要枚舉這個(gè)上升子序列倒數(shù)第二個(gè)數(shù)是什么就好了。

?          狀態(tài)轉(zhuǎn)移：dp[i]=max{ dp[j] | a[j]<a[i] && j<i } 1 ; （dp記錄的是長(zhǎng)度）

?          之前的例子：

?          A：{2 , 5  , 3 , 4 , 1 , 7 , 6}

?          dp[1]=1;

?          dp[2]=max{dp[1]} 1;

?          dp[3]=max{dp[1]} 1;

?          dp[4]=max{dp[1],dp[3]} 1;

?          時(shí)間復(fù)雜度 O（n^2）。

?          在這個(gè)問(wèn)題的分析中，突破口？

?          1：設(shè)計(jì)出了dp[1..n]這個(gè)可以儲(chǔ)存以i結(jié)尾的子序列中最優(yōu)的答案，這個(gè)狀態(tài)表示。

?          2：通過(guò)分析問(wèn)題成功能將當(dāng)前狀態(tài)的最優(yōu)值能過(guò)由之前狀態(tài)轉(zhuǎn)移出來(lái)。dp[i]=max{ dp[j] | a[j]<a[i] && j<i } 1 ，狀態(tài)轉(zhuǎn)移。

>時(shí)間復(fù)雜度

• 套上之前的公式：狀態(tài)數(shù)×狀態(tài)轉(zhuǎn)移復(fù)雜度。

• 狀態(tài)數(shù)：dp[1..n]，只有n個(gè)狀態(tài)。

• 狀態(tài)轉(zhuǎn)移：dp[i]=max{ dp[j] | a[j]<a[i] && j<i } 1 ;

• 由于你每次都需要枚舉之前的所有數(shù)，所以單次轉(zhuǎn)移是O（n）。

• 所以總復(fù)雜度 O（n^2）。

>最長(zhǎng)上升子序列核心代碼

?     設(shè)dp[i]為以a[i]為末尾的最長(zhǎng)上升子序列的長(zhǎng)度。

?     狀態(tài)轉(zhuǎn)移：dp[i]=max{ dp[j] | a[j]<a[i] && j<i } 1 ;

>乘積最大

?          設(shè)有一個(gè)長(zhǎng)度為N的數(shù)字串，要求選手使用K個(gè)乘號(hào)將它分成K 1個(gè)部分，找出一種分法，使得這K 1個(gè)部分的乘積能夠?yàn)樽畲蟆?/p>

?          有一個(gè)數(shù)字串：312，當(dāng)N=3，K=1時(shí)會(huì)有以下兩種分法：

?          1)  3*12=36

?          2)  31*2=62

?          這時(shí)，符合題目要求的結(jié)果是：31*2=62

?          現(xiàn)在，請(qǐng)你幫助你的好朋友XZ設(shè)計(jì)一個(gè)程序，求得正確的答案。

?          N，K（6≤N≤80，1≤K≤50）

>Solution

?          用 f[i][a] 表示前 i 位數(shù)包含 a 個(gè)乘號(hào)所能達(dá)到的最大乘積，我們只需要枚舉上一個(gè)乘號(hào)所在的位置即可。

?          將 j 從 a 到 i - 1 進(jìn)行一次枚舉，表示前 j 位中含有 a-1 個(gè)乘號(hào)，且最后一個(gè)乘號(hào)的位置在 j 處。那么當(dāng)最后一個(gè)乘號(hào)在 j 處時(shí)最大值為前 j 位中含有 a - 1 個(gè)乘號(hào)的最大值乘上 j 處之后到i的數(shù)字。

?          因此得出了狀態(tài)轉(zhuǎn)移方程 f[i][a] = max(f[i][a] , f[j][a-1] * cut(j 1,i))

——（cut(b 1,i) 表示 b 1 到 i 位數(shù)字）

       （枚舉乘號(hào)的位置）

?          然后再寫(xiě)個(gè)高精度即可。

> bzoj4247: 掛飾

?          N個(gè)裝在手機(jī)上的掛飾。掛飾附有可以掛其他掛件的掛鉤。每個(gè)掛件要么直接掛在手機(jī)上，要么掛在其他掛件的掛鉤上。直接掛在手機(jī)上的掛件最多有1個(gè)。此外，每個(gè)掛件有一個(gè)安裝時(shí)會(huì)獲得的喜悅值，用一個(gè)整數(shù)來(lái)表示，可能為負(fù)。

?          想要選出一些掛飾掛在一起，最大化所有掛飾的喜悅值之和。

?          1<=N<=2000
           0<=Ai<=N(1<=i<=N)表示掛勾的數(shù)量
           -10^6<=Bi<=10^6(1<=i<=N)表示喜悅值。

>Solution

?          首先貪心的想，如果最終選出的一組掛飾，肯定是從上到下先掛所含掛鉤多的。所以先按照掛鉤數(shù)量從大到小排序。

Why？？

（1）0       100   掛鉤數(shù)  喜悅值

（2）1  100

亂序ans為100

?          然后設(shè)dp[i][j]前i個(gè)掛飾，剩余j個(gè)掛鉤的最大喜悅值是多少即可。

?          轉(zhuǎn)移枚舉下一個(gè)掛飾是否掛。

?          掛，掛鉤數(shù)更新就j-1 a[i 1]，對(duì)應(yīng)的修改喜悅值；不掛，掛鉤數(shù)就直接轉(zhuǎn)移過(guò)來(lái)

?         dp[i][j]=max(dp[i-1][j],dp[i-1][max(j-a[i],0) 1] v[i])

?          注意dp[i][0]不能轉(zhuǎn)移。

?          （充分描述盡量簡(jiǎn)潔，什么影響問(wèn)題就把什么記下來(lái)）

LIS相關(guān)問(wèn)題

>洛谷P1233 木棍加工

?          一堆木頭棍子共有n根，每根棍子的長(zhǎng)度和寬度都是已知的。棍子可以被一臺(tái)機(jī)器一個(gè)接一個(gè)地加工。機(jī)器處理一根棍子之前需要準(zhǔn)備時(shí)間。準(zhǔn)備時(shí)間是這樣定義的：

?          第一根棍子的準(zhǔn)備時(shí)間為1分鐘；

?          如果剛處理完長(zhǎng)度為L(zhǎng)，寬度為W的棍子，那么如果下一個(gè)棍子長(zhǎng)度為L(zhǎng)i，寬度為Wi，并且滿足L>＝Li，W>＝Wi，這個(gè)棍子就不需要準(zhǔn)備時(shí)間，否則需要1分鐘的準(zhǔn)備時(shí)間；

?          計(jì)算處理完n根棍子所需要的最短準(zhǔn)備時(shí)間。比如，你有5根棍子，長(zhǎng)度和寬度分別為(4, 9)，(5, 2)，(2, 1)，(3, 5)，(1, 4)，最短準(zhǔn)備時(shí)間為2（按(4, 9)、(3, 5)、(1, 4)、(5, 2)、(2, 1)的次序進(jìn)行加工）。

?          N<=5000

>Sloution

?          按w從大到小排序，w相同的l從大到小排序，我們對(duì)于1分鐘能處理的一串棍子實(shí)際上就是一個(gè)l的不上升子序列，我們這里是求一個(gè)不上升子序列覆蓋數(shù)。

?         不上升子序列覆蓋數(shù)=最長(zhǎng)上升子序列長(zhǎng)度。

?          (嚴(yán)格證明參考：dilworth定理)

?          所以其實(shí)就是求一個(gè)最長(zhǎng)上升子序列即可。

    對(duì)于本題，不上升子序列覆蓋數(shù)就是不上升子序列的個(gè)數(shù)

> P1091合唱隊(duì)形

?          N 位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的( N?K )位同學(xué)出列，使得剩下的 K 位同學(xué)排成合唱隊(duì)形。

?          合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為 1,2,…，他們的身高分別為 T_1,T_2,…,T_K

?          則他們的身高滿足 T1<T2<T3..<Ti>T_i 1> ...>Tk

?          你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。

?          n<=100000

>Solution

?          我們?cè)O(shè)f[i]表示以i結(jié)尾的最長(zhǎng)上升子序列長(zhǎng)度。

?          我們?cè)O(shè)g[i]表示以i開(kāi)頭的最長(zhǎng)下降子序列長(zhǎng)度。

?          然后我們枚舉哪一個(gè)為中心的最高點(diǎn)，f[i] g[i]-1取最大值即可。

對(duì)DP優(yōu)化的初探

>LIS加強(qiáng)版

?          求最長(zhǎng)上升子序列。

?          N<=10^5

?          用另兩種方法。

>Sloution

>LIS 分析性質(zhì)

?     狀態(tài)轉(zhuǎn)移：dp[i]=max{ dp[j] | a[j]<a[i] && j<i } 1 ;

?     我們觀察一下這個(gè)dp式子的轉(zhuǎn)移,他到底是在做一個(gè)什么操作。

?     我們是找比a[i]小的a[j]里面,dp[j]的最大值。

?     從這個(gè)角度不是很好優(yōu)化，我們考慮另外一個(gè)思路,我們找最大的k，滿足存在dp[j]==k&&a[j]<a[i]。

?     我們?cè)O(shè)h[k]表示dp[j]==k的所有j當(dāng)中的最小的a[j]，就是說(shuō)長(zhǎng)度為k的最長(zhǎng)上升序列，最后一個(gè)元素的最小值是多少，因?yàn)樽詈笠粋€(gè)元素越小，肯定后面更容易再加上一個(gè)元素了。 (h[k]記錄長(zhǎng)度為k的序列的最后一個(gè)數(shù)字)

?     然后我們發(fā)現(xiàn)了個(gè)奇妙的性質(zhì)。

?     而h[k]，肯定是單調(diào)不下降的，就是說(shuō)“長(zhǎng)度為k的最長(zhǎng)上升序列最后一個(gè)元素的最小值”一定是小于“長(zhǎng)度為k 1的最長(zhǎng)上升序列最后一個(gè)元素的最小值”，如果不是的話，我們可以用后者所在上升子序列構(gòu)造出一個(gè)更小的前者。

?     然后這個(gè)樣子我們對(duì)于一個(gè)a[i]就可以找到,最大的k，滿足h[k]是小于a[i]的，然后f[i]=k 1。 找的過(guò)程是可以二分加速的。

?     然后同時(shí)在維護(hù)出h數(shù)組即可。

>方法1：

?          二分  數(shù)組維護(hù)  單點(diǎn)更新

?          dp[i]的答案就是在h[1]~h[i-1]里面進(jìn)行二分，找到最后一個(gè)小于等于a[i]的數(shù)，那個(gè)數(shù)的下標(biāo)再加一就是dp[i]的答案

 
>方法2：數(shù)據(jù)結(jié)構(gòu)無(wú)腦暴力優(yōu)化

?        數(shù)據(jù)結(jié)構(gòu)不需要什么靈巧的閃光就是套路。

?     狀態(tài)轉(zhuǎn)移：dp[i]=max{ dp[j] | a[j]<a[i] && j<i } 1 ;

?     我們把a(bǔ)[j]看成坐標(biāo)，dp[j]看成權(quán)值，這就是每次求坐標(biāo)小于等于某個(gè)值的權(quán)值最大值，然后每算完一個(gè)單點(diǎn)修改即可。

?     線段樹(shù)能做，但是大材小用了。

?     其實(shí)樹(shù)狀數(shù)組就可以解決。

LCS相關(guān)問(wèn)題

>最長(zhǎng)公共子序列

?          給定兩個(gè)字符串S和T，長(zhǎng)度分別為n和m，求解這兩個(gè)字符串的最長(zhǎng)公共子序列（Longest Common Sequence）。

?          比如字符串S：BDCABA；字符串T：ABCBDAB

?          則這兩個(gè)字符串的最長(zhǎng)公共子序列長(zhǎng)度為4，最長(zhǎng)公共子序列是：BCBA。

?          n,m<=1000

>Solution

?          我們?cè)O(shè)dp[i][j]表示，S串的第i個(gè)前綴和T串的第j個(gè)前綴的最長(zhǎng)公共子序列。

?          分情況：

?          如果S[i]==T[j]，dp[i][j]=dp[i-1][j-1] 1;

?          如果S[i]!=T[j]，dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

?          最后答案就是dp[n][m]

?          對(duì)于dp[i][j]：

?          如果，兩個(gè)串最后一個(gè)位置相同，這兩個(gè)位置一定在公共子序列中。

?          那么我們只需要求出S的i-1前綴和T的j-1前綴的最長(zhǎng)上升子序列就可以了，而這個(gè)就是把問(wèn)題化小。

?          如果最后一個(gè)位置不相同，那么兩個(gè)位置一定不能匹配，所以肯定是另外兩種情況選最大的。

>幾種dp的思考思路

?          大師：根據(jù)經(jīng)驗(yàn)和直覺(jué)設(shè)計(jì)dp狀態(tài)然后轉(zhuǎn)移。

?          一般1：考慮結(jié)尾，分幾種情況，發(fā)現(xiàn)可以轉(zhuǎn)化為形式類(lèi)似的子問(wèn)題，根據(jù)這個(gè)類(lèi)似的形式，設(shè)計(jì)狀態(tài)。

?          （一般是只有一個(gè)結(jié)尾的問(wèn)題我們這么考慮，對(duì)于多個(gè)結(jié)尾的（LIS），直接考慮一個(gè)分部即可。）

?          一般2：考慮搜索，然后轉(zhuǎn)成記憶化再到遞推：搜索->記憶化搜索->遞歸變遞推。

?          搜索搜啥就記下來(lái)啥

(下面沒(méi)看明白)

>最長(zhǎng)公共上升子序列LCIS——分析性質(zhì)優(yōu)化狀態(tài)轉(zhuǎn)移

?          給兩個(gè)序列A長(zhǎng)度為n和B長(zhǎng)度為m，求最長(zhǎng)的公共子序列，還要保證這個(gè)序列是上升的。

> LCIS

?          其實(shí)這是一類(lèi)套路，只不過(guò)這種套路可以考場(chǎng)上自己推出來(lái)，而不是由他人教。當(dāng)然有些套路，比如網(wǎng)絡(luò)流dinic算法怎么寫(xiě)，這個(gè)自己推就費(fèi)勁了。但是這題是完全可以自己研究出來(lái)的。

>Sloution

N^3：

我們?cè)O(shè)dp[i][j]表示A前i個(gè)位置和B前j個(gè)位置所能產(chǎn)生的最長(zhǎng)公共上升子序列的長(zhǎng)度。

N^2

?          我們?cè)O(shè)dp[i][j]表示A前i個(gè)位置和B前j個(gè)位置所能產(chǎn)生的最長(zhǎng)公共上升子序列的長(zhǎng)度。其中強(qiáng)制A[i]==B[j]，也就是最后這個(gè)位置是匹配的。若是A[i]!=B[j]則對(duì)應(yīng)函數(shù)值為0。

?          我們從1到n枚舉i計(jì)算dp值，在枚舉i的過(guò)程中維護(hù)

?          f[k]=max{dp[1…(i-1)][k]}

?          然后dp[i][j]=max{f[k] | k<j && B[k]<A[i]}，如果我們?cè)購(gòu)男〉酱竺杜ej的話只要邊枚舉j邊記錄滿足條件的f[k]最大值即可。

?          總復(fù)雜度O(n*m)

枚舉

相等才算入答案

Tmp是前面合法的dp值中最大的那個(gè)，b[i]比a[i]小，接上才合法

比如我們算dp[4][5],那我們算3，4這一塊的就行了，當(dāng)算dp[4][6]，也就是有一個(gè)維度增加了，所以我們只需要算dp[3][4]和dp[1-3][5]，那么就是少了一個(gè)維度，所以復(fù)雜度變成了n^3

 > Bzoj5124波浪序列

>Sloution

?          和LCIS完全一樣的解法啊。

?          設(shè)f[i][j][0/1]表示第一個(gè)序列前i和第二個(gè)序列前j個(gè)位置，最后一個(gè)位置是上升還是下降，轉(zhuǎn)移和之前一樣，記錄一個(gè)輔助數(shù)組即可。

?          注意這里是記方案數(shù)。

DP與容斥初步

最基本的容斥模型：

?          給定一些條件, 問(wèn)全部滿足的對(duì)象的個(gè)數(shù)。

?          答案 = 所有對(duì)象 - 至少不滿足其中一個(gè)的 至少不滿足其中兩個(gè)的 - 至少不滿足其中三個(gè)的 ……

?          證明：考慮對(duì)于一個(gè)恰好不滿足k個(gè)的的對(duì)象，被計(jì)算了幾次。

?         

?          顯然只有當(dāng)k=0時(shí)，這個(gè)對(duì)象才會(huì)被算進(jìn)答案

?          K=1時(shí)，算出來(lái)=0

?          因?yàn)樯厦娴氖阶涌梢杂啥?xiàng)式定理變化一下：
∑(i=0~k) (-1) ⁱ* ( 1^k-1 ) * C( _kⁱ )

?          PS:二項(xiàng)式定理（x y）ⁿ=∑(i=0~k) xⁱ * y^k-i * C(_nⁱ)

?          所以我們就證明了上面這個(gè)容斥方法的正確性。

>Bzoj3782 簡(jiǎn)化版（網(wǎng)格路徑計(jì)數(shù) 強(qiáng)化版）

?          從n*m網(wǎng)格圖的左下角走到右上角(n,m<=10^8),有t個(gè)坐標(biāo)不能經(jīng)過(guò)(t<=200),只能向上向右走,問(wèn)有多少種不同的走法,對(duì)10^9 7取模。

>Solution

?         Dp是處理計(jì)數(shù)問(wèn)題應(yīng)該非常常用的方法，而計(jì)數(shù)問(wèn)題又常常與容斥原理相結(jié)合。

?          考慮t=1的情況,我們只需要把總的路徑條數(shù)減去經(jīng)過(guò)那個(gè)障礙點(diǎn)的路徑條數(shù)就可以了。走法=”左下角到障礙點(diǎn)的走法”*”障礙點(diǎn)到右上角的做法”

?          t=2時(shí),設(shè)兩個(gè)障礙點(diǎn)為A,B,”總的路徑條數(shù)”-“經(jīng)過(guò)A的路徑條數(shù)”-“經(jīng)過(guò)B的路徑條數(shù)”算出來(lái)的答案可能偏小,如果A,B可以同時(shí)經(jīng)過(guò),那么最終答案要加上”同時(shí)經(jīng)過(guò)A,B的路徑條數(shù)”。

?          那么這道題就可以用容斥來(lái)做。隨意填-至少遇到一個(gè)障礙的方案數(shù) 至少遇到兩個(gè)障礙的方案數(shù)-至少遇見(jiàn)三個(gè)障礙的方案數(shù)………………

?          給障礙點(diǎn)從左到右從下到上排個(gè)序,記f[i][j]表示走到了第i個(gè)障礙點(diǎn)且包括第i個(gè)點(diǎn)在內(nèi)強(qiáng)制經(jīng)過(guò)了j個(gè)障礙點(diǎn)的路徑條數(shù)(除此之外也可能有經(jīng)過(guò)的),枚舉上一個(gè)經(jīng)過(guò)的障礙點(diǎn)即可。

?          轉(zhuǎn)移的時(shí)候乘上一個(gè)組合數(shù)表示從k到i的走法數(shù)目

>另一種容斥的方法

?          另一種形式的容斥dp，枚舉第一個(gè)遇到的障礙是哪一個(gè)來(lái)容斥。

?          實(shí)際上這是由下面這個(gè)推出來(lái)的。

記憶化搜索

先搜索然后發(fā)現(xiàn)可以記憶化，然后記下來(lái)

>網(wǎng)格圖路徑計(jì)數(shù)

?          給出一個(gè)n*m的網(wǎng)格，每次只能向右或者向下走，求從(1,1)走到(n,m)的方案數(shù)，其中有些位置是不能走的。

?         

?n,m<=1000

>Sloution

?          我們從另一個(gè)角度來(lái)思考這個(gè)問(wèn)題。

?          我們用搜索算法來(lái)計(jì)算答案，先看看沒(méi)有障礙的情況，有障礙只改一點(diǎn)。

?          然而搜索的時(shí)間復(fù)雜度是指數(shù)級(jí)的。

?          觀察一下：這是有些重復(fù)計(jì)算的。

?          我們發(fā)現(xiàn)在這個(gè)dfs的過(guò)程中，dfs出來(lái)的值只與帶入?yún)?shù)，也就是(x,y)有關(guān)，而不同的(x,y)有N*M個(gè)，而我們之前搜索的問(wèn)題在于有大量的重復(fù)計(jì)算，多次調(diào)用同一個(gè)(x,y)，每次都從新計(jì)算。

?          有一個(gè)很直觀的想法就是，第一次調(diào)用的時(shí)候就把答案記下來(lái)，之后調(diào)用 不重新算，直接返回之前已經(jīng)計(jì)算出 的答案即可?！@就是記憶化搜索。

?          mp[x][y]==-1表示有障礙

記憶化搜索：看題先搜索，然后發(fā)現(xiàn)參數(shù)種類(lèi)不多，maybe多次調(diào)用同一個(gè)參數(shù)，記下來(lái)減少重復(fù)計(jì)算

>滑雪

?          給定一個(gè)區(qū)域，由一個(gè)二維數(shù)組給出。數(shù)組的(i,j)代表點(diǎn)(i,j)的高度。我們要找一個(gè)最長(zhǎng)的滑雪路徑，注意滑雪只能從高往低處滑。下面是一個(gè)例子。

?           1  2  3  4 5

?          16 17 18 19 6

?          15 24 25 20 7

?          14 23 22 21 8

?          13 12 11 10 9

?          解釋?zhuān)阂粋€(gè)人可以從某個(gè)點(diǎn)滑向上下左右相鄰四個(gè)點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-...-3-2-1更長(zhǎng)。事實(shí)上，這是最長(zhǎng)的一條。

>Solution

?          dp[x][y]存儲(chǔ)在當(dāng)前位置下山的最大長(zhǎng)度，它等于 它旁邊的（上下左右）比它矮的山的dp值加1 的最大值，即

?          dp[x][y]=max(dp[x-1][y] , dp[x][y-1] , dp[x][y 1] , dp[x 1][y]) 1。

?          要保證對(duì)應(yīng)的高度小于H[x][y]才能取max。

?          1：一般遞推式動(dòng)態(tài)規(guī)劃還要注意枚舉狀態(tài)的順序，要保證算當(dāng)前狀態(tài)時(shí)子狀態(tài)都已經(jīng)算完了。

?          2：但是記憶化搜索不需要，因?yàn)橛洃浕阉骶褪莻€(gè)搜索，只不過(guò)把重復(fù)的部分記下來(lái)了而已。我們不用像遞推一樣過(guò)于關(guān)注順序，像搜索一樣直接要求什么，調(diào)用什么就好。

>記憶化搜索

?          在有一些dp問(wèn)題中，狀態(tài)之間的轉(zhuǎn)移順序不是那么確定，并不能像一些簡(jiǎn)單問(wèn)題一樣寫(xiě)幾個(gè)for循環(huán)就解決了。

?          我們可以直接計(jì)算最終要求的狀態(tài)，然后在求這個(gè)狀態(tài)的過(guò)程中，要調(diào)用哪個(gè)子狀態(tài)就直接調(diào)用即可，但是每一個(gè)狀態(tài)調(diào)用一遍之后就存下來(lái)答案，下次計(jì)算的時(shí)候就直接取答案即可，就不需要從新再計(jì)算一遍。

?          雖然看上去每一次都計(jì)算不少，但是因?yàn)槊恳粋€(gè)狀態(tài)都計(jì)算一次，所以均攤下來(lái)，復(fù)雜度還是狀態(tài)數(shù)*狀態(tài)轉(zhuǎn)移。

>bzoj3810

>Solution

?          思路：手玩數(shù)據(jù)，找出最優(yōu)子結(jié)構(gòu)，做dp。關(guān)鍵是找出劃分狀態(tài)的方式。

?          考慮分割成兩個(gè)矩形，對(duì)于任意一種分割方案都一定存在一條貫穿橫向或者縱向的線，那么枚舉這條線即可。

?          然后設(shè)f[x][y][t]表示長(zhǎng)為x寬為y，面向大海的邊狀態(tài)是t，最小的不滿意度。轉(zhuǎn)移就枚舉從那個(gè)地方斷開(kāi)即可。

?          主程序如下：

?          紅色是面向大海的部分。

?          記憶化搜索部分并不難，主要是分情況套論別漏下什么就好。

拓?fù)鋱DDP

?          拓?fù)鋱Ddp通常是在拓?fù)鋱D上求關(guān)于所有路徑的某種信息之和。當(dāng)然這里的“和”的運(yùn)算法則可以是加法或是取max和min。或者其他定義的運(yùn)算。

?          按拓?fù)湫?strong>沿著有向邊轉(zhuǎn)移就可以了。

>BZOJ4562 食物鏈

?          給定n個(gè)點(diǎn)m條邊的有向無(wú)環(huán)食物網(wǎng)，求其中有多少條極長(zhǎng)食物鏈。

?          n<=10^5，m<=2*10^5

>Solution

?          拓?fù)鋱Ddp經(jīng)典題

?          設(shè)f[u]為以節(jié)點(diǎn)u為終點(diǎn)的食物鏈數(shù)量。

?          按照拓?fù)湫虻捻樞蜣D(zhuǎn)移即可。

?          上面的式子是求一個(gè)點(diǎn)時(shí)，枚舉其所有入邊轉(zhuǎn)移，具體寫(xiě)代碼的時(shí)候，我們一般就只記出邊再記錄一個(gè)入邊太麻煩了。所以我們一般不枚舉入邊，而是枚舉出邊從每個(gè)點(diǎn)往后更新，也就是在上面的式子中，我們對(duì)于每個(gè)v向后進(jìn)行更新，枚舉v出邊指向的所有u點(diǎn)，然后f[u] =f[v]。

>拓?fù)鋱Ddp

?          其實(shí)我們對(duì)于一般非有關(guān)期望和概率的dp，如果題目中每一個(gè)轉(zhuǎn)移關(guān)系是雙邊的，那么如果我們把dp的每一個(gè)狀態(tài)記為一個(gè)點(diǎn)， dp狀態(tài)之間關(guān)系構(gòu)成的圖就是一個(gè)拓?fù)鋱D。

?          拓?fù)鋱Ddp實(shí)際上就是已經(jīng)給了我們這個(gè)拓?fù)潢P(guān)系了，也就不需要我們自己找了，其實(shí)是更簡(jiǎn)單。

>經(jīng)典題            

?          給一個(gè)n個(gè)點(diǎn)m條邊的無(wú)向圖，每一條邊(u,v)有兩個(gè)參數(shù)(len,cnt)表示邊的長(zhǎng)度以及邊上不同的禮物數(shù)量，我們?cè)诿恳粋€(gè)走過(guò)的邊(u,v,len,cnt)只能選1個(gè)禮物，選擇的方案數(shù)是cnt。

?          我們現(xiàn)在想從S走到T，我們想要求出在只走最短路徑的情況下有多少種選擇的禮物的方案數(shù)。

?          一條路徑選擇禮物的方案數(shù)就是每條邊的cnt的乘積。答案對(duì)一個(gè)大質(zhì)數(shù)取模。

?          n<=100000,m<=300000

>Solution

?          (u,v,len,cnt)其實(shí)就是(u,v)點(diǎn)對(duì)有cnt條長(zhǎng)度len為邊，求S到T的最短路徑方案數(shù)。

?          求以最短路徑為前提的一些問(wèn)題，果斷先建最短路圖。

?          畢竟，最短路圖建出來(lái)是一個(gè)DAG，而DAG就比隨意的圖具有更好的性質(zhì)，不求白不求。

?          u,v,len

?          If(dis[u] len==dis[v])  len在最短路徑上

?          然后就是求DAG上從S到T，路徑的方案數(shù)。

?          設(shè)f[u]為從u到T路徑的方案數(shù)，

?          答案就是f[S]。

?          記憶化搜索代碼實(shí)現(xiàn)

>一道難(mei)題(jiang)

>bzoj4055 misc

?          給定n個(gè)點(diǎn)m條邊的無(wú)向圖，每個(gè)點(diǎn)有點(diǎn)權(quán)Ai，每條邊有長(zhǎng)度和寬度，定義一條路徑的寬度為路徑上所有邊的寬度的乘積。

?          記f(s,t)為s到t的所有最短路徑的寬度之和，f(s,t,v)為s到t的所有最短路徑中經(jīng)過(guò)v的路徑的寬度之和。

?          對(duì)每個(gè)點(diǎn)v，求：

?          n<=1000，m<=4000

>Solution

?          枚舉上式中的s，考慮該s對(duì)每個(gè)v的貢獻(xiàn)。

?          還是先求出以s為起點(diǎn)的最短路徑DAG，可以用DAGdp對(duì)每個(gè)t求出f(s,t)。

?          f(s,t,v)=f(s,v)*DAG上v到t的每條路徑的寬度之和。

?          記后者為g(v,t)，則 F(v) = A_sf(s,v) ∑ g(v,t)*A_t/f(s,t)

?          F(v) = A_sf(s,v) ∑ g(v,t)*A_t/f(s,t)

?          A_t/f(s,t)可以看做每個(gè)t自帶的權(quán)值。

?          設(shè)G[u]表示以u(píng)為起點(diǎn)的所有路徑的寬度與其終點(diǎn)權(quán)值乘積之和。

?          G[u]=∑ w(u,v)*(G[v] A_v/f(s,v)) | (u,v)∈DAG

?          F(v) =A_sf(s,v)G[v]

?          按拓?fù)湫虻剐騞p即可，記憶化也行。

基礎(chǔ)DP練習(xí)題

>最大子矩陣

?          在n*n的整數(shù)矩陣中找一個(gè)最大的子矩陣，最大化元素和。

?          N<=100

>Solution

?          枚舉上下邊界，然后只需要確定左右邊界，就是個(gè)一維的問(wèn)題，實(shí)際上就是求最大連續(xù)子段和。

?          F[i]=max(0,f[i-1]) val[i];

?          val[i]表示枚舉的上下界范圍內(nèi)第i列的和。

The end  推薦一道卡長(zhǎng)練習(xí)題

P4604 [WC2017]挑戰(zhàn)