數字三角形系列，數字三角形

數字三角形系列，數字三角形

---

P1044 數字三角形 時間: 1000ms / 空間: 131072KiB / Java類名: Main

背景

09年 USACO 11月月賽  銅牌第一道

---

描述

示出了一個數字三角形。 請編一個程序計算從頂至底的某處的一條路
徑，使該路徑所經過的數字的總和最大。
　　每一步可沿左斜線向下或右斜線向下走；
　　1<三角形行數<25；
　　三角形中的數字為整數<1000；

---

輸入格式

第一行為N，表示有N行
後面N行表示三角形每條路的路徑權

輸出格式

路徑所經過的數字的總和最大的答案

---

測試樣例1

輸入

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

輸出

30

---

備注

搜索80分，記憶化搜索AC

---

    　　記憶化搜索，從後往前訪問。對於每一個點正常往下走時有兩種不同走法，於是從上往下走時只需逆推即可。所以對於a[i][j]而言，只需加上a[i+1][j]與a[i+1][j+1]中的最大值。不斷循環最後得到最大值為a[1][1]。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[30][30],n;
 7 int main()
 8 {
 9     cin>>n;
10     for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);
11     for(int i=n-1;i>=0;i--)
12     {
13         for(int j=1;j<=i;j++)
14         { 
15               a[i][j]+=max(a[i+1][j+1],a[i+1][j]); 
16         }
17     }
18     cout<<a[1][1]<<endl;
19     return 0;
20 }

---

 

 

P1076 數字三角形2 時間: 1000ms / 空間: 131072KiB / Java類名: Main

描述

數字三角形
要求走到最後mod 100最大

---

輸入格式

第1行n，表示n行 <=25
第2到n+1行為每個的權值

---

輸出格式

mod 100最大值

---

測試樣例1

輸入

2 
1 
99 98

輸出

99

---

    　　這題tyvj的數據非常詭異，想騙分的朋友輸出99會發現自己奇妙的得了90分。