<style> .reveal .slides { text-align: left; font-size:28px; } </style> # DP Introduction to Competitive Programming 5/17 ---- ## 上課內容 - 最大子矩形 * 最大正方形 * 單調棧 * 最大長方形 - 懸線法 - DP on Tree * 基礎樹上 DP * 樹上背包問題 * 換根 DP --- ## 最大子矩形 ---- ## 最大正方形 題目敘述 : 給你一個只有 $0$ 和 $1$，大小為 $n \cdot m$ 的矩陣，求出一個只包含 $1$ 的最大正方形，並輸出邊長。 ---- 作法 1 : 那大家應該都還記得這個東西 [前綴和](https://hackmd.io/@LeeShoWhaodian/MATandBitwise#/3/3) 就會發現這題可以使用前綴和解決，那就需要枚舉二維 $i$ $j$ $k$ 分別為現在的 $x$ 座標 $y$ 座標以及正方形邊長 $z$ ，時間複雜度 $O(nml)$ 於是就可以產生出 code ---- ```cpp for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { for(int l=1;l<=size;l++) { int x=i+l-1; int y=j+l-1; if(x>n || y>m || sum[x][y]-sum[x][j-1]-sum[i-1][y]+sum[i-1][j-1]!=l*l) break; if(ans<l) ans=l; } } ``` ---- 作法 2 : 該好好做的DP，狀態轉移式為 : ```cpp if (a[i][j]==1) dp[i][j]=min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]})+1; ``` 對於 $dp[i][j]$ 的定義是，以節點 $i$ $j$ 為右下角時，可構成的最大正方形邊長 $dp[i][j]$，而只有 $a[i][j]$ 為 $1$ 時才可以轉移，因此code如下 ---- ```cpp for (int i=1;i<=n;++i){ for (int j=1;j<=m;++j){ cin>>a[i][j]; if(a[i][j]) dp[i][j]=min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]})+1; ans=max(ans,dp[i][j]); } } ``` 同時會發現，很明顯裡面只用到 $i-1$ 與 $j-1$ ，因此可以空間壓縮成 $O(M*2)$，同時也可以拓展成更高維的題目，像是詢問最小立方體體積。 ---- ## 單調棧 顧名思義，單調棧即滿足單調性的 stack 結構。與單調隊列相比，其只在頂端進行 in/out 的操作，也就是stack跟deque的差別。 那就可以發現，在stack裡面要滿足單調性，你就需要不斷檢查他頂端的元素，直到你即將放入的元素比你頂端的元素 大/小 ```cpp void Insert(x){ while(!sta.empty()&&sta.top()<x) sta.pop(); sta.push(x); } ``` ---- [例題](http://poj.org/problem?id=3250) 題目敘述 : 給定數字 $n$ 及長度為 $n$ 的整數陣列，其中 $a_i$ 代表第 $i$ 個人的高度，詢問每個人往右看可以看到多少人。 example ```cpp 6 10 3 7 4 12 2 ``` 第一步把 ${10,0}$ 入隊，然後把 ${3,1}$ 入隊，對 ${3,1}$ 來說，左邊第一個數字就比他大，他對答案的貢獻為 $1-0-1=0$。 然後把 ${7,2}$ 入隊，由於需要滿足單調性因此 ${3,1}$ pop掉，對 ${7,2}$ 來說，他對答案的貢獻為 $2-0-1=1$ 。 ---- ## 最大長方形/最大子矩陣 題目敘述 : 給你一張只有 $0$ 和 $1$，大小為 $n \cdot m$ 的矩陣，求出一個只包含 $1$ 的最大子矩形，並輸出邊長。 那在這邊可以使用懸線法，而需要先知道的是，懸線法的適用範圍是單調 stack 的子集，也就是你在使用的時候需要滿足以下條件(會發現就是可以很簡單便捷的在stack上解決) : * 序列符合單調性 * 可以在單調 stack 上解決 * 不能在 stack 上二分搜 ---- 那為何不直接學習單調 stack 呢，原因是因為懸線法比起單調 stack 更容易學習且容易理解，而他的具體用法則是可以直接配合題目使用。 [例題題敘](https://www.luogu.com.cn/problem/SP1805) : 在一條水平線上有 $n$ 個寬度為 $1$ 的矩形，求最大子矩形面積。 而懸線就是有一條直線，你要對每個節點向左向右查看最遠可以到哪裡，利用這條直線直接使用 $O(n)$ 跑過一次 ---- 想法 : 針對每個節點要查看的是 1. 是否在邊界，若是在邊界則無法繼續拓展 2. 對 $arr_i$ 來說是否大於 $arr_{l_{i-1}}$ ，若大於則代表這條線也無法往左邊拓展 (對右邊同理)  ---- code: ```cpp const int N = 1e5+5; int n, a[N],l[N], r[N]; long long ans; int main() { while (cin>>n) { ans = 0; for (int i = 1; i <= n; i++) cin>>a[i], l[i] = r[i] = i; for (int i = 1; i <= n; i++) while (l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1]; for (int i = n; i >= 1; i--) while (r[i] < n && a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1]; for (int i = 1; i <= n; i++) ans = max(ans, (long long)(r[i] - l[i] + 1) * a[i]); cout<<ans<<"\n"; } } ``` ---- [例題 玉蟾宫](https://www.luogu.com.cn/problem/solution/P4147) 敘述 : 給定一個 $n \times m$ 的包含 $'F'$ 和 $'R'$ 的矩陣，求其面積最大的子矩陣的面積 $\times 3$ ，且目標子矩陣中的每一位的值都為 $'F'$ 解法 : 你會發現這題的模型跟上一題非常相似，而我們在這題要做的就只是先確定每一個直行的所有元素，而他直行的元素就是懸線法裡面的垂線，使他的 $(x,y)$ 線盡可能的向上擴展(也就是讓他變大)，然後在對直行做懸線法，你會發現 $a[j]$ 就是橫排連通幾個區塊，那最大子矩陣一定就會在這某些線的左右拓展之中。 而懸線的想法就可以讓程式碼變成 $O(n \cdot m)$ ---- code : ```cpp for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { //初始化 l[j] = r[j] = j; } char c; for (int j = 1; j <= m; j++) { //對每一個直行做統計，若是上一個a[j]也是1則會變成2 cin>>c; if (c == 'F') a[j]++; else if (c == 'R') a[j] = 0; } for (int j = 1; j <= m; j++) while (l[j] != 1 && a[l[j] - 1] >= a[j]) l[j] = l[l[j] - 1]; for (int j = m; j >= 1; j--) while (r[j] != m && a[r[j] + 1] >= a[j]) r[j] = r[r[j] + 1]; for (int j = 1; j <= m; j++) ans = max(ans, (r[j] - l[j] + 1) * a[j]); } ``` --- ## tree DP 樹形 DP，即在樹上進行的 DP。由於樹固有的遞迴性質，樹形 DP 一般都是遞迴進行的。 ---- ## 基礎樹上DP 其實和一般的DP一樣是重要在轉移式上面，通過 DFS 遞迴往最深層，然後在返回上一層時更新當前結點的最優解，以此從根開始 DFS 即可得到答案。 ---- [例題 沒有上司的舞會](https://www.luogu.com.cn/problem/P1352) 題目敘述 : 給你一棵樹，每個節點有權值，選擇最多節點使總和最大，限制為若選擇了一個節點，則不能選擇他的父節點。 這是一道很經典而且適合練手的好題，那會發現當我們從根節點開始 dfs 的時候，我們是否選擇當下的節點會對之後的選擇有後效性，因為是否選擇此節點會對其他子節點的選擇會有影響，因此很顯然是不行的。 於是這種時候就需要多開一維，配合起來才可以接受，$dp[i][j]$ 表示以 $i$ 為根時子樹的最優解 $dp[i][j]$ 的 $j$ 為 $0/1$ 表 $i$ 不選擇或是 $i$ 被選擇，以及再 dfs 返回上一層的時候更新答案。 ---- 對於每個狀態，都存在兩種決策（其中下面的 $x$ 都是 $i$ 的兒子）： 1. 不選擇父節點時，子節點可以選擇，也可以不選擇，此時有 $f(i,0) = \sum\max\{f(x,1),f(x,0)\}；$ 2. 選擇父節點時，子節點絕對不能選，此時有 $f(i,1) = \sum{f(x,0)} + a_i$。 ---- 於是就可以得出以下code: ```cpp void calc(int k) { vis[k] = 1; for (int now : edge[k]) { // 枚舉該節點的每個子節點 if (vis[now]) continue; calc(now); f[k][1] += f[now][0]; f[k][0] += max(f[now][0], f[now][1]); // 轉移方程 } return; } int main() { cin>>n; for (int i = 1; i <= n; i++) cin>>f[i][1]; for (int i = 1; i < n; i++){ cin>>l>>k; is_root[l] = 1; //紀錄根 edge[l].push_back(k); } for (int i = 1; i <= n; i++) if (!is_root[i]) { // 從root開始DFS calc(i); cout<<max(f[i][1], f[i][0])<<"\n"; return 0; } } ``` ---- ## 樹上背包 是一種算常見的題型，很好的結合了樹上 DP 以及背包 DP 的問題，混合兩個的核心想法 ---- [例題 選課](https://www.luogu.com.cn/problem/P2014) 題目敘述 : 現在有 $n$ 門課程，第 $i$ 門課程的學分為 $a_i$，每門課程有零門或一門先修課，有先修課的課程需要先學完其先修課，才能學習該課程。 一位學生要學習 $m$ 門課程，求其能獲得的最多學分數。 可以想像成先修課就是那門課的父節點，於是你就會發現它給的一張圖就是一張森林，那我們要做的第一件事情就是創造一個 ${0,0}$ 的node，而其是指向所有樹上的根節點，讓這個森林形成一棵樹。  ---- 於是就可以假設 $f(x,i,j)$ 表示以 $x$ 號點為根的子樹中，已經遍歷了 $x$ 號點的前 $i$ 棵子樹，選了 $j$ 門課程的最大學分。 那我們只需要枚舉 $x$ 的每個子節點 $y$ ，然後枚舉每個 $y$ 選擇課程的方案，再返回到 $x$ 那層，使用到背包的想法去做樹上的dp，可以得出以下轉移方程 : $f(x,i,j)=\max_{k \leq j,k \leq \textit{siz_y}} f(y,i-1,j-k)+f(y,s_y,k)$ ```cpp //s_y y的子節點數量 //siz_y 以y為根的子樹大小 //須注意的是選擇的課程數量 j 不能 > m ``` 那這時候我們的 $dp[x][i][j]$ 會發現可以把 $[i]$ 維壓掉(滾動數組)，所以會剩下 $dp[x][j]$ ，意義為 $x$ 為根的子樹選擇了 $j$ 堂課的最大學分。 所以 $dp[0][m+1]$ 就是答案，因為你會算是需要多選 $0$ 那堂課，因此需要額外加 $1$ 。 ---- 所以很輕鬆的code就出來了 ```cpp int dfs(int u) { int p = 1; //已選課堂數 dp[u][1] = s[u]; for (int v : edge[u]) { int siz = dfs(v); for (int i = min(p, m + 1); i; i--) //不倒序的話會重複選取 for (int j = 1; j <= siz && i + j <= m + 1; j++) dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]); //去掉一維後的轉移式 p += siz; } return p; } ``` ---- ## 換根 DP 換根 DP 在中國又稱為二次掃描，顧名思義就是需要做兩次 dfs 掃描就可以知道結果，其中第一次 dfs 通常是預處裡，像是深度, 點權, 距離, 子樹數量之類的訊息。而第二次 dfs 就是核心，利用前面知道的訊息進行換根 DP。 ---- [簡單例題-樹上點塗色](https://codeforces.com/problemset/problem/1324/F) 題目敘述 : 給定一棵 $n$ 個點的樹，每個節點為黑色或白色其中一種，對於每個節點，要找出包括自己所有可能的連通子圖中，白色節點個數 - 黑色節點個數最大的數量。 那首先會很明顯的發現對於這個樹來說，誰當根節點都是一樣的意思，所以第一次 DFS 就可以節點 $1$ 下手，每次要紀錄的是對於 $dp[i]$ 對 $1$ 為根的子樹來說所有點的 $dp$ 值。 然後第二次換根就很簡單只需要紀錄 從 $f_x$ 轉移到 $f_y$ 的時候對 $dp$ 值的貢獻會是 $dp[x] - max(0 , dp[y])$ $dp[y] + max(0 , dp[x])$ 因為如果是負數我們大可不必選擇那個子樹。 然後我們再使用 $dfs(y, x)$ 去遍歷即可，等遞迴回到此層的時候再回朔。 ---- ```cpp void dfs(int x,int fa){//第一次DFS 求出以1為根節點時的所有dp值 dp[x]=a[x]?1:-1; //若為白色就是1 黑色就是-1 這樣子樹總和即代表差值 for(int i : edge[x]){ if(i==fa)continue; dfs(i,x); dp[x]+=max(0,dp[i]); //紀錄以 1 為根的dp值 } } void dfs0(int x,int fa){//第二次DFS換根 ans[x]=dp[x];//答案數組 for(int y : edge[x]){ if(y==fa)continue; dp[x]-=max(0,dp[y]),dp[y]+=max(0,dp[x]); //轉移式 dfs0(y,x); dp[y]-=max(0,dp[x]),dp[x]+=max(0,dp[y]); //回朔 } } ``` ---- [例題-距離](https://www.luogu.com.cn/problem/P3478) 題目敘述 : 給你一棵樹，求出當樹上任意一個點為根時，所有節點的節點深度總合最大。 那我們的第一次 DFS 預處裡就是需要先處理所有的 $s_i$ (以 $i$ 為根時的子樹數量)，處裡完後，我們一樣以 $x$ 當作目前節點， $y$ 作為他的子節點，接下來就是展現換根精隨的地方了。 ---- 令 $ans_i$ 是以 $i$ 為根時所有節點的節點深度總合，當我們把 $ans_x$ 轉移到 $ans_y$ 的時候，深度會發生變化的有兩種，分別是 所有在 $y$ 的子樹上的節點深度都減少了一，那麼總深度和就減少了 $ans_y$ 所有不在 $y$ 的子樹上的節點深度都增加了一，那麼總深度和就增加了 $n-ans_y$ 知道這兩個變化後，就可以知道轉移式如下 : $ans_y = ans_x - s_y + n - s_y$ 也就是說可以推論出轉移式 : $ans_y = ans_x + n - 2 \cdot s_y$ 於是只要再 DFS 遍歷一次即可求出答案 ---- 具體code: ```cpp void dfs(int u, int fa) { // 預處裡dfs sz[u] = 1; // 以 u 為根的子樹數量 dep[u] = dep[fa] + 1; // u 的深度 for (int v : edge[u]) { //遍歷 u 的子節點 if (v != fa) { //不等於父親 dfs(v, u); sz[u] += sz[v]; } } } void get_ans(int u, int fa) { // 第二次dfs換根dp for (int v : edge[u]) { //遍歷子節點 if (v != fa) { dp[v] = dp[u] - sz[v] * 2 + n; //轉移式 get_ans(v, u); } } } ``` --- 本日作業 : https://vjudge.net/contest/556548