3176 Cow Bowling

PKU


牛がボーリングするらしいよ…

問題文は謎だったけど、要するに２分木の根から葉までのスコアの最大値を求めるものらしい。

以前の俺ならすべてのパス（2^N個）のスコアを計算しようという愚行をしでかしていただろう。

だがッッ！！今の俺にはDPがいるッッッ！！

だからやってみた。


dp[i][j]をi列目の第jピンをパスに含めるときの、根からそのピンまでのスコアの最大値とする。

  • dp[1][1]はまぁ第１ピン。
  • dp[i][j](2<=i<=N, 1<=j<=i)はdp[i-1][j-1]とdp[i-1][j]の大きい方。

できたできた。scanfしたらそのままdp[i][j]を計算するという進歩！（以前なら一回ピンの配置を配列に確保してただろう）

ピンのスコアとして負の値が入ってくることを懸念してdpをINT_MINで初期化した版(47MS)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>

using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int dp[N+2][N+2];
    for (int i = 0; i < N+2; ++i) {
        for (int j = 0; j < N+2; ++j) {
            dp[i][j] = INT_MIN;
        }
    }
    int ans = 0;
    scanf("%d", &dp[1][1]);
    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j <= i; ++j) {
            int p;
            scanf("%d", &p);
            dp[i][j] = p + max(dp[i-1][j-1], dp[i-1][j]);
            if (i == N) ans = max(ans, dp[i][j]);
        }
    }
    printf("%d", ans);
}

みんなの見たらおろろが0MSだったから、dpを0で初期化してみた版(32MS)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>

using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int dp[N+2][N+2];
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    scanf("%d", &dp[1][1]);
    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j <= i; ++j) {
            int p;
            scanf("%d", &p);
            dp[i][j] = p + max(dp[i-1][j-1], dp[i-1][j]);
            if (i == N) ans = max(ans, dp[i][j]);
        }
    }
    printf("%d", ans);
}

0MSの出し方plz＞＜