A41024. 三角形
填空题
中等
知识点
题目描述
三角形
题目描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
上述表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。
每一步只能由当前位置向左下或右下。
输入格式
你的程序要能接受标准输入。第一行包含一个整数T，表示总的测试次数。
对于每一种情况：第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。
接下来的N行输入表示三角形的每一行的元素Ai,j，其中0 < Ai,j < 100。
输出格式
输出每次测试的最大值并且占一行。
样例输入
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
参考答案
#include <iostream>
using namespace std;
int Max(int a,int b);
int main()
{
int dp[100][100],num,x,t=0,t1=0;
cin>>num;
while (num--)
{
cin>>x;
for (;t<x;t++)
{
for (t1=0;t1<=t;t1++)
cin>>dp[t][t1];
}
for (t=x-2;t>=0;t--)/*换层循环，层数向上增加*/
{
for (t1=0;t1<=t;t1++)/*每一行求最优*/
dp[t][t1]=dp[t][t1]+Max(dp[t+1][t1+1],dp[t+1][t1]);/*从下向上开始查找，逐步找最优解*/
}
t=0;
t1=1;
cout<<dp[0][0]<<endl;
}
return 0;
}
int Max(int a,int b)
{
return a>b?a:b;
}
上一题
下一题