【移動類DP】數字三角形4

Description

一個數字三角寶塔。

設數字三角形中的數字為絕對值不超過1000的整數。

小K從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。

每走過一個節點他會把這個節點的數字加在自己計數器中。

另外他有一次機會，将目前位置上的數字清零，他可以在任意時刻使用這次機會。

現在小K想知道他到達底層後，計數器中可能的最大的值.

Input

輸入資料的第1 行是數字三角形的行數n，1<=n<=1000。

接下來n行是數字三角形各行中的數字。所有數字都小于1000。

Output

程式運作結束時，将計算出的最大值輸出。

Sample Input

5
-1
-8 -7
3 3 -2
-3 -2 -5 -4
7 -3 -9 -10 -3
           

Sample Output

6
           

分析

相對于前面幾個題，很明顯的是這個題二維的（i，j）已經不夠描述狀态了，是以我們再加上第三維k，表示走到目前位置時是否使用過清零機會。

如果走到目前位置時還沒有使用過清零機會，那就正常的更新就好；

如果使用過了，那麼目前狀态更新為max( dp ( pre, 0 ) ) 和 max ( dp ( pre, 1 ) + a)的最大值。

狀态轉移方程：

dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][0]) + a[i][j];
dp[i][j][1] = max(max(dp[i - 1][j][0], dp[i - 1][j - 1][0]), max(dp[i - 1][j][1], dp[i - 1][j - 1][1]) + a[i][j]);
           

代碼

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1010][1010];
int dp[1010][1010][2];
int ans = -1e9;
 
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}
 
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            a[i][j] = read();
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j][0] = dp[i][j][1] = -1e9;
        }
    }
    dp[1][1][0] = a[1][1];
    dp[1][1][1] = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][0]) + a[i][j];
            dp[i][j][1] = max(max(dp[i - 1][j][0], dp[i - 1][j - 1][0]), max(dp[i - 1][j][1], dp[i - 1][j - 1][1]) + a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, max(dp[n][i][0], dp[n][i][1]));
    }
    printf("%d", ans);
    return 0;
}
           

此題還有另一種思路

先預處理出每個點往上走和往下走能走出的最大值，然後枚舉被清零的那個點，利用預處理出的值更新ans

代碼沒寫。