AcWing 3304. 数字三角形
原题链接
简单
作者:
隐灵
,
2024-03-30 16:02:58
,
所有人可见
,
阅读 2
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N][N], f[N][N]; //DP
int n;
int main()
{
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 - 1], f[i - 1][j]) + a[i][j]; //从左上方和右上方取一个最大值
if (n % 2) printf("%d\n", f[n][n / 2 + 1]); //当n是奇数时,落点一定在最中间
else printf("%d\n", max(f[n][n / 2], f[n][n / 2 + 1])); //当n时偶数时,落点一定在中间的两点间
return 0;
}