网站如何paypal支付,网站空间如何申请,wordpress 建站对比,网站双倍浮动[USACO1.5] [IOI1994]数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径#xff0c;使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中#xff0c;从 7 → 3 → 8 →…[USACO1.5] [IOI1994]数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中从 7 → 3 → 8 → 7 → 5 7 \to 3 \to 8 \to 7 \to 5 7→3→8→7→5 的路径产生了最大权值。
输入格式
第一个行一个正整数 r r r ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
样例 #1
样例输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5样例输出 #1
30提示
【数据范围】 对于 100 % 100\% 100% 的数据 1 ≤ r ≤ 1000 1\le r \le 1000 1≤r≤1000所有输入在 [ 0 , 100 ] [0,100] [0,100] 范围内。
题目翻译来自NOCOW。
USACO Training Section 1.5
IOI1994 Day1T1 思路
使用一个二维数组 a 存储数字三角形的值使用一个二维数组 dp 存储从顶点到每个位置的最大路径和。
状态转移方程
dp[i][j] max(dp[i - 1][j - 1], dp[i - 1][j]) a[i][j];在初始化 dp 数组时dp[0][0] 赋值为 0。
在每次状态转移时判断上一行的相邻两个位置的最大值加上当前位置的值得到当前位置的最大路径和。
最后遍历最后一行的所有位置取最大值即可。 AC代码
#include iostream
#include algorithm
#define AUTHOR HEX9CF
using namespace std;const int N 1e3 5;int r;
int ans;
int a[N][N];
int dp[N][N];int main()
{cin r;for (int i 1; i r; i){for (int j 1; j i; j){cin a[i][j];}}dp[0][0] 0;for (int i 1; i r; i){for (int j 1; j i; j){dp[i][j] max(dp[i - 1][j - 1], dp[i - 1][j]) a[i][j];}}ans 0;for (int j 1; j r; j){// cout dp[r][j] endl;ans max(ans, dp[r][j]);}cout ans endl;return 0;
}
