三角形——题解

解题思路:

此题一般的迭代解法在遇到较大规模的测试时会需要花费大量时间，从而导致程序通不过，比如我一开始用的如下解法：

#include<iostream>

#include<vector>

using namespace std;

int max(int m,int n)

{

return m>n? m:n;

}

int f(vector<vector<int> > &str,int i,int j)

{

int n=str.size()-1;

if(i==n-1)

return str[i][j]+max(str[i+1][j],str[i+1][j+1]);

else

return str[i][j]+max(f(str,i+1,j),f(str,i+1,j+1));

}

int main()

{

int T;

cin>>T;

while(T-->0)

{

int N;

cin>>N;

vector<vector<int> >str(N,vector<int>(N));

for(int i=0;i<N;i++)

for(int j=0;j<=i;j++)

cin>>str[i][j];

int sum=f(str,0,0);

cout<<sum<<endl;

}

return 0;

}

在遇到第7个测试时时间会超限，所以我们换一下思路，从三角形的顶点到三角形任一行的某一点都存在一个最大路径，也就是除去终点外该路径所经过的数值之和最大，我们可以在获取三角形具体值时，同时记录下这个最大值和所到终点的和，那么最后我们只需要遍历最后一行的记录值就可以获得整个三角形的路径最大值。举例列子：

1  //总测试次数
5  //三角形行数
7  //此行开始是三角形
3 8
8 1 0  
2 7 4 4
4 5 2 6 5

对于三角形顶点“7”，由于它没有前置的行数，所以此处的记录值就是7；

对于第二行：先看“3”，该点左上方和正上方的点都可以到达它（由于左上方不存在，所以忽略），正上方点的记录值是7，那么该点记录值就是“7+3=10”；来看“8”，它的左上方和正上方（正上方不存在所以忽略），仅左上方可以到达它，所以记录值为“7+8=15”。

对于第三行：“8”，只有正上方能达到它，所以记录值为正上方记录值与该点记录值之和“10+8=18”；来看“1”，它的左上方和正上方都可以到达它，也就是“3”和“8”，因为是记录最大路径的值所以比较这两点的记录值：10和15，15较大，所以该点的记录值就位“1+15=16”；“0”类似。

下面的行类似。

注意事项:

三角形每一行的最左端和最右端都只有一条路径可以到达，在代码实现是要考虑到这一点。

参考代码:

#include<iostream>

#include<vector>

using namespace std;

struct anker

{

int a;

int sum;

};

int max(int m,int n)

{

return m>n? m:n;

}

int main()

{

int T;

cin>>T;

while(T-->0)

{

int N;

cin>>N;

vector<vector<anker> >str(N,vector<anker>(N));

for(int i=0;i<N;i++)

for(int j=0;j<=i;j++)

{

cin>>str[i][j].a;

if(i==0)

str[i][j].sum=str[i][j].a ;

else

{

if(j-1<0)

str[i][j].sum=str[i][j].a +str[i-1][j].sum ;

else

str[i][j].sum =str[i][j].a +max(str[i-1][j-1].sum,str[i-1][j].sum );

}

}

int Max=str[N-1][0].sum ;

for(int k=1;k<N;k++)

if(str[N-1][k].sum >Max)

Max=str[N-1][k].sum ;

cout<<Max<<endl;

}

return 0;

}

若有疑问或建议，随时欢迎一起讨论。