當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

The Triangle

發(fā)布時(shí)間：2024/4/30 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了 The Triangle 小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

題目限制

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 59262 Accepted: 35557
時(shí)間限制： 1000ms 內(nèi)存限制： 10000k
提交：59262 接受：35557

Description

描述

73 88 1 02 7 4 44 5 2 6 5

(Figure 1)
Figure 1 shows a number triangle.
圖1顯示了一個(gè)數(shù)字三角形。
Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.
編寫一個(gè)程序，計(jì)算從頂部開(kāi)始，在底部某個(gè)位置結(jié)束的路由上傳遞的最大數(shù)字總和。
Each step can go either diagonally down to the left or diagonally down to the right.
每一步都可以向左斜向下或向右斜向下。

Input

輸入
Your program is to read from standard input.
您的程序?qū)臉?biāo)準(zhǔn)輸入中讀取。
The first line contains one integer N: the number of rows in the triangle.
第一行包含一個(gè)整數(shù)n：三角形中的行數(shù)。
The following N lines describe the data of the triangle.
下面的n行描述了三角形的數(shù)據(jù)。
The number of rows in the triangle is > 1 but <= 100.
三角形中的行數(shù)大于1但小于等于100。
The numbers in the triangle, all integers, are between 0 and 99.
三角形中的數(shù)字，所有整數(shù)，都在0到99之間。

Output

輸出
Your program is to write to standard output.
您的程序?qū)懭霕?biāo)準(zhǔn)輸出。
The highest sum is written as an integer.
最高的和被寫為一個(gè)整數(shù)。

Sample Input

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

Sample Output

30
Source
IOI 1994

解題思路

用二維數(shù)組存放數(shù)字三角形

D（i，j）：第i行第j個(gè)數(shù)字（r，j從1開(kāi)始算）
MaxSum（r，j）：從D（i，j）到底邊的各條路徑，最佳路徑的數(shù)字之和。

問(wèn)題：求MaxSum（1,1）

典型的遞歸問(wèn)題：
D（i，j）出發(fā)，下一步只能走到D（i+1，j）或者D（i+1，j+1）。

遞歸代碼

#include <iostream> #include <algorithm> #define MAX 101 using namespace std; int D[MAX][MAX]; int n; int MaxSum(int i,int j) {if(i==n){return D[i][j];}int x=MaxSum(i+1,j);int y=MaxSum(i+1,j+1);return max(x,y)+D[i][j]; } int main() {int i,j;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>D[i][j];}}cout<<MaxSum(1,1)<<endl;return 0; }

想都不用想，肯定會(huì)：Time Limit Exceeded

為什么會(huì)超時(shí)？

重復(fù)計(jì)算：
如果采用遞歸的方法，深度遍歷每條路徑，存在大量重復(fù)計(jì)算，時(shí)間復(fù)雜度為2ⁿ。

改進(jìn)

如果每算出一個(gè)MaxSum（）就保存起來(lái)，下次用到其值的時(shí)候直接取用，則可免去重復(fù)計(jì)算。
因?yàn)槿切蔚臄?shù)字總數(shù)是n(n+1)/2，那么可以用O（n²）時(shí)間完成計(jì)算。

記憶遞歸型動(dòng)態(tài)規(guī)劃程序

#include <iostream> #include <algorithm> #define MAX 101 using namespace std; int maxSum[MAX][MAX]; int D[MAX][MAX]; int n; int MaxSum(int i,int j) {if(maxSum[i][j]!=-1){return maxSum[i][j];}if(i==n){maxSum[i][j]=D[i][j];}else{int x=MaxSum(i+1,j);int y=MaxSum(i+1,j+1);maxSum[i][j]=max(x,y)+D[i][j];}return maxSum[i][j]; } int main() {int i,j;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>D[i][j];maxSum[i][j]=-1;}}cout<<MaxSum(1,1)<<endl;return 0; }

遞歸轉(zhuǎn)遞推

從下往上，每?jī)蓚€(gè)數(shù)往上找一層最大數(shù)：

#include <iostream> #include <algorithm> #define MAX 101 using namespace std; int D[MAX][MAX],n; int maxSum[MAX][MAX]; int main () {cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>D[i][j];if(i==n) maxSum[n][j]=D[n][j];}}for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];}}cout<<maxSum[1][1]<<endl;return 0; }

空間優(yōu)化

直接用D的最后一行存放maxSum

#include <iostream> #include <algorithm> #define MAX 101 using namespace std; int D[MAX][MAX],n; int * maxSum; int main () {cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>D[i][j];}}maxSum=D[n];for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){maxSum[j]=max(maxSum[j],maxSum[j+1])+D[i][j];}}cout<<maxSum[1]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的The Triangle的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

Triangle