洛谷 P1216 [USACO1.5] [IOI1994]数字三角形题解

本文主要是介绍洛谷 P1216 [USACO1.5] [IOI1994]数字三角形题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

观察题目我们发现从前往后推会有条件判断，不容易写出来。所以就从后往前推。

也就是说后面的状态已经是推出来了，保证是最大值。

//数字三角形
#include<iostream>
using namespace std;
const int N = 510;
int f[N][N], n;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;//初始化for (int i = 1; i <= n; ++i)for (int j = 1; j <= i; ++j) cin >> f[i][j];//从最后一层往前递推for (int i = n - 1; i; --i)for (int j = 1; j <= i; ++j) f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);cout << f[1][1];return 0;
}

最后输出的答案就是第一层所在的位置。

这篇关于洛谷 P1216 [USACO1.5] [IOI1994]数字三角形题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---