poj 3176 Cow Bowling

原题地址

知识点：DP

解题报告

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

using namespace std;

int a[350][350];
int d[350][350];
int N;

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

  d[0][0] = a[0][0];
  for(i=0;i<N-1;++i) {
    for(j=0;j<=i;++j) {
      // 注意这里记忆计算让重叠路径的值最大的技巧
      d[i+1][j+1] = max(d[i+1][j+1], d[i][j] + a[i+1][j+1]);
      d[i+1][j] = max(d[i+1][j], d[i][j] + a[i+1][j]);
    }
  }

  cout << *max_element(d[N-1], d[N-1]+N) << endl;
  return 0;
}