题目链接

Cow Bowling POJ - 3176

思路

经典的数字三角形dp问题 状态转移：
$$ dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j] $$

时间复杂度

$$ O(N^2) $$

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 350 + 10;
const int INF = 0x3f3f3f3f;
int a[MAXN][MAXN];
int main() {
    int n;
    scanf("%d", &n);// don't forget &
    int ans = -INF;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%d", &a[i][j]);// don't forget &
            a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
            ans = max(ans, a[i][j]);
        }
    }
    printf("%d", ans);
    return 0;
}