POJ 1163 The Trangle
题意:
给出一个数字三角形,每个分叉路口可以选择一条道路向下走,获得路上的点的权值。求可以获得的最大权值是多少?
定义状态: 我们需要知道当每个位置的权值,所以定义 \(f[i][j]\) 为到达第 \(i\) 行,第 \(j\) 个点的路径上获得的最大值是多少。
转移方程: \(f[i][j] = a[i][j] = max(f[i + 1],f[i + 1]][j + 1])\)
实现:
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 355;
int a[N][N];
int f[N][N];
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 = n; i >= 1; i--)
{
for (int j = 1; j <= i; j++)
{
f[i][j] = a[i][j];
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
}
}
printf("%d\n", f[1][1]);
return 0;
}
标签:1163,int,POJ,权值,Trangle,include
From: https://www.cnblogs.com/zxr000/p/17001775.html