數字三角形模型

• 前言
• 最低通行費
• 方格取數
• 傳紙條

前言

數字三角形題型的一般描述是：

給定一個共有N行的三角矩陣A，其中第t行有X列。從左上角出發，每次可以向下方或右下方走一步，最終到達底部求把經過的所有位置上的某種最優情況

一般這類題的dp表達式都是：$f[i,j]$

最低通行費

題目轉送門

首先我們定義：$f[i,j]$表示，從（1,1）走到（i，j）的最小花費，我們先不考慮時間是(2n-1)內，對于一個(i,j)我們可以從四個方向進入它，因此有 f[i][j] = min(f[i][j] , f[xx][yy] + a[i][j]) ; 我們按照這個dp式子交上去發現也可以ac，這是因為對于一個(i,j)來說我們在dp的時候是不會選擇走回頭路到（i，j）的也就是從下方和右方進入。
那么結合時間，我們發現我們在不走回頭路的情況下都要（2n - 1）的單位時間，因此我們在考慮時間后可以不用考慮四個方位了。

代碼：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 110 ; int n ; int a[N][N] , f[N][N]; int dx[4] = {1,-1,0,0} , dy[4] = {0,0,1,-1};int main(){cin>>n;memset(f , 0x3f , sizeof f);for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= n ; ++j)cin>>a[i][j];f[1][1] = a[1][1];for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= n ; ++j)for(int k = 0 ; k < 4 ; ++k){int xx = i + dx[k] , yy = j + dy[k];if(xx <= 0 && xx > n && yy <= 0 && yy > n)continue;f[i][j] = min(f[i][j] , f[xx][yy] + a[i][j]) ;}cout<<f[n][n]<<endl;return 0; }

方格取數

題目轉送門

這題由走一篇的最大值，變成看走兩遍的最大值（且不能重復取）。最開始的思路是先走第一篇取得一個最大值，然后標記之后再走一篇，兩者相加，但是這個題貪心的讓兩次都最大并不一定是最優解，
如果遇到兩次能把所有點都踩到的情況：
但由于第一次和第二次沒有聯系，第一次只取最優解，可能會導致第二次不能把剩下的點都踩到。
因此二維無法滿足我們，那么我們就擴大維數，變成：$$f[k][i][j]$
k=i1+j1=i2+j2k=i1+j1=i2+j2 : 兩個小朋友同時走, 每個人走的步數和是一樣的
我們考慮集合劃分

// 需要判斷j是否越界！ #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 15; int n ; int a[N][N] , f[N*2][N][N];int main(){cin>>n;int x,y ,c;while(cin>>x>>y>>c , x || y ||c)a[x][y] = max(a[x][y],c);for(int k = 2 ; k <= n * 2 ; ++k)for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= n ; ++j){int t = a[i][k-i] , &x = f[k][i][j] ;int j1 = k - i , j2 = k - j;if(j1 <= 0 || j1 > n || j2 <= 0 || j2 > n)continue;if(i != j ) t += a[j][k-j];x = max(x,f[k-1][i][j] + t);x = max(x,f[k-1][i][j-1] + t);x = max(x,f[k-1][i-1][j] + t);x = max(x,f[k-1][i-1][j-1] + t);}cout<< f[2*n][n][n] <<endl;return 0; }

傳紙條

題目轉送門

題面分析：在這里我們可以轉變一下思路，把求一條從(1,1) ->(n,m)和(n,m) - > (1,1)總共兩條路徑轉化為，求兩條從，(1,1) --> (n,m)的最大路徑。那么這題就可以直接套用上一題的dp式子了。

要深刻理解dp表達式的含義

代碼：

#include<iostream> #include<algorithm> using namespace std; const int N = 55; int n , m ; int w[N][N] , f[N<<1][N][N];int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j)cin>>w[i][j];for(int k = 2 ; k <= n + m ; ++k)for(int i = 1; i <= n ; ++i)for(int j = 1 ; j <= n ; ++j){int t = w[i][k-i] + w[j][k-j] , &x = f[k][i][j];int j1 = k - i , j2 = k - j;if(j1 <= 0 || j1 > m || j2 <= 0 || j2 > m )continue;if(i != j || k == 2 || k == n + m){x = max(x,f[k-1][i][j] + t);x = max(x,f[k-1][i][j-1] + t);x = max(x,f[k-1][i-1][j] + t);x = max(x,f[k-1][i-1][j-1] + t);}}cout<<f[n+m][n][n]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的动态规划之数字三角形模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。