数字三角形

总时间限制: 1000ms 内存限制: 65536kB

描述

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

      (图1)

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

输入

输入的是一行是一个整数N(100>=N>=1)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

5
7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

样例输出

思路

1.搜索

#include<bits/stdc++.h>

using namespace std;

int a[105][105],s;

int dfs(int i,int j)

{

	if(i==s)

		return a[i][j];

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

}

int main()

{

	cin>>s;

	for(int i=1;i<=s;i++)

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

			cin>>a[i][j];

	cout<<dfs(1,1);

	return 0;

}

时间复杂度为\(O（2^n）\),最大为\(O(2^{100}),\)超时。

2.记忆化搜索

#include<bits/stdc++.h>

using namespace std;

int a[105][105],s,b[105][105];

int dfs(int i,int j)

{

	if(i==s)

		return a[i][j];

	if(b[i][j]!=0)

		return b[i][j];

	b[i][j]=a[i][j]+max(dfs(i+1,j),dfs(i+1,j+1));

	return b[i][j];

}

int main()

{

	cin>>s;

	for(int i=1;i<=s;i++)

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

			cin>>a[i][j];

	cout<<dfs(1,1);

	return 0;

}

由于每个位置只搜索了一次，所以时间复杂度为\(O（n^2）\),通过 ! ! !

3.递推(顺推)

#include<bits/stdc++.h>

using namespace std;

int a[105][105],s;

int main()

{

	cin>>s;

	cin>>a[1][1];

	for(int i=2;i<=s;i++)

	{

		cin>>a[i][1];

		a[i][1]+=a[i-1][1];

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

		{

			cin>>a[i][j];

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

		}

	}

	int maxx=-1;

	for(int j=1;j<=s;j++)

		maxx=max(maxx,a[s][j]);

	cout<<maxx;

	return 0;

}

同样，时间复杂度为\(O（n^2）\),通过。

4.递推(逆推)

#include<bits/stdc++.h>

using namespace std;

int a[105][105],s;

int main()

{

	cin>>s;

	for(int i=1;i<=s;i++)

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

			cin>>a[i][j];

	for(int i=s-1;i>=1;i--)

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

			a[i][j]+=max(a[i+1][j],a[i+1][j+1]);

	cout<<a[1][1];

	return 0;

}

不用多说，时间复杂度也为\(O（n^2）,\)通过。

巴特西

[IOI 1994]数字三角形

数字三角形

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

输入的是一行是一个整数N(100>=N>=1)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出最大的和。

30

思路

1.搜索

2.记忆化搜索

3.递推(顺推)

4.递推(逆推)

&nbsp 以上便是此题的多种解法，欢迎下次再来。

最新文章

热门文章