一本通T1258

SFxuks · 2020-02-29 19:28:46 · 个人记录

T1258

一个形似于杨辉三角的dp，比较显然

#include <bits/stdc++.h>
using namespace std;

int a[1001][1001];
int f[1001][1001];

int main()
{
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= i; j++)
      scanf("%d", &a[i][j]);
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= i; j++)
    {
      f[i][j] = max(f[i - 1][j] + a[i][j], f[i - 1][j - 1] + a[i][j]);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i++) ans = max(ans, f[n][i]);
  printf("%d", ans);
  return 0;
}