POJ_3176: Cow Bowling

3176 -- Cow Bowling

蟻本の動的計画法の練習問題として解いた。

挙げられる課題として、

・サンプルの読み違え 　⇒読んだ

これに尽きる。簡単な問題なので瞬殺したい。

あとPOJで”#include <bits/stdc++.h>”は使えないみたい。ヘッダーもちゃんと意識しなきゃいけないな。

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[350][350],N,ma;

int main(){
  scanf("%d",&N);

  for(int i=0;i<N;i++)
    for(int j=0;j<i+1;j++) scanf("%d",&dp[i][j]);

    for(int i=1;i<N;i++){
      for(int j=0;j<i+1;j++){
        if(j==0) dp[i][j]+=dp[i-1][j];
        else if(j==i) dp[i][j]+=dp[i-1][j-1];
        else dp[i][j]+=max(dp[i-1][j-1],dp[i-1][j]);
      }
    }

    for(int i=0;i<N;i++) ma=max(ma,dp[N-1][i]);

    printf("%d\n",ma);

    return 0;

}