Poj 3176: Cow Bowling

poj3176.md

Poj 3176: Cow Bowling

題目

分析

DP 水題。

dp[row][col] = row, col 以下小三角形的最大和

轉移方程式：

dp[row][col] = max(dp[row+1][col], dp[row+1][col+1]) + data[row][col]

答案為 dp[0][0] 。

AC Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int data[350][350];
int dp[350][350];

int solve() {
    memset(dp, 0, sizeof(dp));
    memcpy(dp[N-1], data[N-1], sizeof(int) * N);
    for (int row = N-2; row >= 0; row--) {
        for (int col = 0; col <= row; col++) {
            dp[row][col] = max(dp[row+1][col], dp[row+1][col+1]) + data[row][col];
        }
    }
    return dp[0][0];
}

int main() {
    scanf("%d", &N);
    for (int row = 0; row < N; row++)
        for (int col = 0; col <= row; col++)
            scanf("%d", &data[row][col]);
    printf("%d\n", solve());

    return 0;
}