Day 3 上午
內容提要：
動態規劃
數位DP
樹形DP
區間DP
?
動態規劃
斐波那契數列
f(0)=0,f(1)=1,......,f(n)=f(n-1)+f(n-2)
0,1,1,2,3,5,8,13......
他和動態規劃有什么關系？
首先，他有一個邊界條件，就是f(0)=0,f(1)=1，相當于它不是從正無窮到負無窮都有定義的數列
像這種規定好的條件，我們把它叫做 邊界條件（不依賴其他值就能直接得到）
f(n)=f(n-1)+f(n-2)
f(n)的值依賴于前兩項斐波那契數列的值
這個式子就叫做動態規劃中的 轉移方程
每一個f(0),f(1),....,f(n)就叫做動態規劃中的 狀態
無后效性等價于有向無環圖（DAG）這里先暫時不提
對于一個動態規劃題，我們只需要確定狀態，邊界條件，轉移方程，剩下的就只剩下寫代碼了
有三種不同的寫法
1.順著推
2.倒著推
（名字起得好隨意，其實就是遞推和遞歸）
3.記憶化搜索
?
int n,f[233];int main() {cin>>n;f[0]=0;f[1]=1;for(int a=2;a<=n;a++){f[a]=f[a-1]+f[a-2];}cout<<f[n]; }
?
?
數組f代表狀態，f(i)代表第i項
先定義邊界狀態
然后寫轉移方程
這是逆著推
for(int a=0;a<n;a++) {f[a+1]+=f[a];f[a+2]+=f[a]; } cout<<f[n];
?
順著推
想f(a)會影響那些斐波那契的值
?
int dfs(int n) {if(n==0) return 0;if(n==1) return 1;return dfs(n-1)+dfs(n-2); } int main() {cin>>n;cout<<dfs(n)<<endl;return 0; }
?
?
?
逆著推是當你算f(a)的時候，你要去算他
順著推是當你算好f(a)的時候，你用f(a)去更新別人
兩種寫法在某些時候會有復雜度的區別
記憶化搜索
記憶化搜索的核心是搜索
以斐波那契數列為例：
如果我們直接搜索，搜到1就返回1，搜到0就返回0的話，這個代碼的復雜度是f(f(n))，因為f(n)是由一個一個f[1]=1累加起來的
斐波那契通項公式是指數級的，所以當n很大時，復雜度就gg
記憶化：
int f[n];bool suan_le_mei[n];int dfs(int n) {if(n==0) return 0;if(n==1) return 1;if(suan_le_mei[n]) return f[n];suan_le_mei[n]=true;f[n]=dfs(n-1)+dfs(n-2); } int main() {cin>>n;cout<<dfs(n)<<endl;return 0; }
?
因為當你算f(n)時要算f(n-2)，算f(n-1)時也要算f(n-2)，但是由于f(n-2)的值不變，所以它重復了
記憶化搜索就是保證每一個f(n)在搜索中只被算一次
所以我們兩個數組
一個表示第i項的值
一個表示第i項有沒有被算過
為了避免重復計算，我們要先看它有沒有被算過
一旦算過就直接返回這一項的值
否則就先把它標記為算過，再dfs前兩項計算這一項的值
這樣寫的話復雜度就變成了O(n)，因為每個值只被算了一次
一般來說它用不上，但是要知道怎么寫
矩陣優化的話復雜度就變成了O(log n) 鏈接
常見的動規種類：
數位DP
樹形DP
狀壓DP
區間DP
其他DP（其他是個什么鬼呦~）
還有兩種NOIP中基本不會涉及
插頭DP
博弈論DP
一般來說每一年NOIP中至少會出一道DP題
但是令人吃鯨的是：最大概率考的是其他DP（鬼才出題人）
先來看四種有套路的
數位DP：
看一個非常簡單的題
讀入兩個正整數l，r，問你從l到r中有多少個正整數
答案顯然是r-l+1
（但是我們要挑戰自己，所以來個數位dp
[l,r]數的個數=[0,r]數的個數-[0,l-1]數的個數
我們就把問題化成了求[0,x]這段區間之間有多少個數
把x的十進制表示寫出來
X=XnXn-1....X0
數位dp的核心思想就是按照十進制位從高到低一位一位進行dp
剛才的問題等價于看有多少個v滿足0≤v≤x
V=VnVn-1...V0
如果有Vn=0就說明有前導0
給VnVn-1...V0每一個數填上0~9之間的某一個看有多少方案滿足v≤x
數位dp填數的時候是從高往低填的
比如當你填Vn-3時，Vn-2，Vn-1,Vn已經填好了
比較兩個數的大小從高往低比較
我們希望填上Vn-3后，v的前四位≤x的前四位
分情況討論：
1.x前三位＞v前三位，此時Vn-3可以填0~9的任何一個數
2.x前三位=v前三位，為了保證填了這一位有v的前四位≤x的前四位，我們能填的數就是0~Xn-3
數位dp的數組一般至少有兩個維度
f[i][j]
i表示已經填到了第i位
j取值要么是0，要么是1
j=0：表示x的前i位數＞v的前i位數
j=1：表示x的前i位數=v的前i位數
f[i][j]表示這種情況下的方案數
轉移：我們去枚舉第i-1位填什么，然后就轉移到f[i-1][j']上
這就是數位dp的一個核心思路
代碼奉上：
1 int solve(int x) 2 { 3 int n=0; 4 while(x) 5 { 6 z[n]=x%10; 7 x/=10; 8 n++; 9 } 10 n--; 11 12 memset(f,0,sizeof(f)); 13 14 f[n+1][1]=1; 15 16 for(int a=n;a>=0;a--) 17 { 18 for(int b=0;b<=1;b++) 19 { 20 if(b==0) 21 { 22 for(int c=0;c<=9;c++) 23 f[a][0]+=f[a+1][b]; 24 } 25 else 26 { 27 for(int c=0;c<=z[a];c++) 28 { 29 if(c==z[a]) f[a][1]+=f[a+1][b]; 30 else f[a][0]+=f[a+1][b]; 31 } 32 } 33 } 34 } 35 return f[0][0]+f[0][1]; 36 } 37 38 int main() 39 { 40 cin>>l>>r; 41 cout<<solve(r)-solve(l-1)<<endl; 42 return 0; 43 }
注意這里要進行兩次dp，所以進行下一次dp之前要請空數組
我們發現當填第n位時，要從第n+1位轉移過來
但是n+1位都是0，所以他們相等
所以我們令f[n+1][1]=1
考慮從第n位到第a+1位是相等還是小于
然后分情況討論，枚舉0和1
如果b=0，第a位就可以填0~9的任何一個數
如果b=1，第a位就可以填0~z[a]之間的數
然后再次討論填的數是否=z[a]
答案是小于的方案加上等于的方案
?
Problem 2
求在[l,r]中的數的數位之和
?
把之前的代碼稍微改一下
代碼：
int l,r,z;int f[23333][2]; int g[23333][2]; int solve(int x) {int n=0;while(x){z[n]=x%10;x/=10;n++;}n--;memset(f,0,sizeof(f));memeste(g,0,sizeof(g));f[n+1][1]=1;g[n+1][1]=0;//因為第n+1位是0 for(int a=n;a>=0;a--){for(int b=0;b<=1;b++){if(b==0){for(int c=0;c<=9;c++){f[a][0]+=f[a+1][b];//每一個方案對數位之和貢獻一個c g[a][0]+=g[a+1][b]+f[a+1][b]*c;}}else {for(int c=0;c<=z[a];c++){if(c==z[a]) {f[a][1]+=f[a+1][b];g[a][1]+=g[a+1][b]+f[a+1][b]*c;}else {f[a][0]+=f[a+1][b];g[a][0]+=g[a+1][b]+f[a+1][b]*c;}}}}}return g[0][0]+g[0][1]; }int main() {cin>>l>>r;cout<<solve(r)-solve(l-1)<<endl;return 0; }
改造改造就好了
Problem 3
求在[l,r]中滿足十進制位中相鄰兩個數字之差至少為2的數有多少個
既然多了一個條件，最直接的方法就是增加一個維度，變成一個三維狀態
f[i][j][k]
i和j一樣
k表示第i位填了k
保證第i位和第i+1位的差至少為2
洛谷P2657 windy數
?
樹形dp
舉一個栗子:
給你一顆n個點的樹，問這棵樹有多少個點？、
顯然是n個點
（但是我們要挑戰自己，所以我們選擇用樹形dp
（顯然是閑得蛋疼）
對于樹形dp來說，這棵樹一定會有一個根
不能再往下走的點就是葉子節點
以某個點為根的子樹就是它能到達的所有點形成的樹
以根節點為根的子樹所對應的顯然就是整棵樹
f[i]代表以i為根的子樹有多少個點
如果根節點是1的話，我們最終要求的顯然就是f[1]
邊界條件？f[leaf]=1 葉子節點所對應的子樹大小就是1
顯然它是從下往上推的
所以我們在算到p的時候，他下面的都已經被算完了
f[p]=f[son1]+f[son2]+...+f[sonk]+1（k為兒子的個數）
以p為根的子樹大小=它所有兒子的子樹大小之和+1
偽代碼：
int f[233];void dfs(int p) {for(x is p''s son)//枚舉x是p的兒子 {dfs(x);f[p]+=f[x]; }f[p]++; }int main() {cin>>n;//點數 read_tree();//讀入樹//由于它是從下往上，所以我們選用dfsdfs[1];cout<<f[1]<<endl;return 0; }
?
又一個栗子：
給你一個n個點的樹，求它的直徑
直徑：在這棵樹上找到兩個點，使它們的距離最遠
考慮一棵子樹內的直徑怎么算
從一個點走到另一個點的過程盡可能大
樹狀路徑一定是向上走到某一個點，在向下走到某一個點
從一個點向下走兩條路，兩條路拼起來后形成一條路徑
要讓這兩條路徑都盡可能長
也就是從一個點向下走最長和次長的路徑拼起來，就是以這個點為拐點的最長路徑
f[i][0]代表i向下最長路徑的長度
f[i][1]代表i向下次長路徑的長度
算一個點的答案，要把它所有兒子的答案整合起來
f[p][0]=max(f[p1][0],f[p2][0],...f[pk][0])+1
假如最大是p2
如果我們把f[p2][0]換成f[p2][1]可以嗎？
不行！
因為如果f[p1][0]最長，f[p2][1]次長，就會重復走，這顯然是不合法的
我們不如直接把它去掉
f[p][1]=max(f[p1][0],,...f[pk][0])+1
區間dp
洛谷P1880 合并石子
有n堆石子，你只能合并相鄰兩堆石子
a1,a2,a3,....,an
合并一次 n-1 堆石頭
合并兩次 n-2 堆石頭
求最小代價
合并相鄰，把所有的合并為一個：區間dp
狀態一定是f[l][r]，代表把l和r合并的最小代價
讓我們回到這個題
這個題求的是f[1][n]
先定義狀態：f[l][r]
邊界：f[i][i]=0當你只有一堆石頭時，合并代價是0
最后一次合并一定是把兩堆石頭合并成一堆石頭
合并石頭并不會改變原本的順序，所以最后一次合并一定可以找到一條分界線，使得左邊為l，右邊為r
合并左邊：f[l][p] 合并右邊：f[p+1][r]
轉移方程:f[l][r]=min(f[l][p]+f[p+1][r]+sum[l][r])
思路：枚舉斷點
代碼：
int z[manx],f[maxn][maxn];int main() {cin>>n;for(int a=1;a<=n;a++)cin>>z[a];//表示石子數memset(f,0x3f,sizeof(f));//初始化為無窮大 for(int a=1;a<=n;a++)f[a][a]=0;//枚舉左端點，右端點，斷點 for(int l=1;i<=n;l++)//枚舉左端點 {for(int r=l+1;r<=n;i++)//枚舉右端點 {for(int p=l;p<r;p++){f[l][r]=min(f[l][r],f[l][p]+f[p+1][r]+sum[l][r]);//左邊合并的代價+右邊合并的代價+這段區間的石子之和 }}}cout<<f[1][n]<<endl; return 0； }
石子之和用前綴和計算就好了
代碼非常的簡單易懂對吧
但是
這是不對的！
(驚不驚喜，意不意外，刺不刺激
為什么呢？
?
因為它不滿足dp的階段性
因為你算f[1][n]時要用到f[2][n]，但它還沒有被算過
我們注意到長的區間都是由短的區間拼起來的，所以我們枚舉區間長度
int z[manx],f[maxn][maxn];int main() {cin>>n;for(int a=1;a<=n;a++)cin>>z[a];//表示石子數memset(f,0x3f,sizeof(f));//初始化為無窮大 for(int a=1;a<=n;a++)f[a][a]=0;for(int len=2;len<=n;len++)//枚舉區間長度 {for(int l=1,r=len;r<=n;l++,r++)//枚舉區間位置 {for(int p=l;p<r;p++){f[l][r]=min(f[l][r],f[l][p]+f[p+1][r]+sum[l][r]);//左邊合并的代價+右邊合并的代價+這段區間的石子之和 }}}cout<<f[1][n]<<endl; return 0； }
復雜度O(n^3)
但是第1堆和第n堆是相鄰的
怎么處理？
如果直接在最后一堆后面再加上一個第一堆石頭，這樣答案就不一定是f[1][n]了
它還有可能是f[2][n+1]
就是min(f[1][n],f[2][n+1])
但是這樣a1和a2就不相鄰了
在最后再加上a2
這樣繼續下去，把石子弄成a1,a2,....,an,a1,a2,....,an
ans=min(f[1][n],f[2][n+1],f[3][n+2],f[4][n+3]....)
每次合并兩個相鄰的東西相當于去掉一條邊
只需要合并n-1次，這樣的話至少有一條邊沒有用到，可以看成把這條邊斷開，就變成了斷開的答案
所以我們剛才就是在枚舉到底斷開哪一條邊
仍然是一遍dp，只不過區間變成了兩邊
?
轉載于:https://www.cnblogs.com/lcezych/p/10794212.html
總結
- 上一篇： 电影《狂蟒之灾》的内容是？类似《狂蟒之灾
- 下一篇： “未霜荷已败”下一句是什么