国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

小鑫去爬山

2019-11-11 00:31:50

字體：大中小

供稿：網(wǎng)友

PRoblem Description

馬上就要放假了，小鑫打算去爬山。小鑫要去爬的這座山有n個海拔區(qū)間。為了清楚描述我們可以從上到下標(biāo)號1到n。第i個區(qū)間有i個落腳點，每一個落腳點都有一個危險值。小鑫需要在第n個海拔區(qū)間挑選一個點向上爬，爬到第1個海拔區(qū)間（也就是山頂）。他必須規(guī)劃一條路徑，讓危險值之和最小。這樣才安全的。并不是任意兩個落腳點之間都可以相互到達(dá)。我們這樣定義對于第i個（i<n）區(qū)間的第j個落腳點，只有第i+1個區(qū)間的第j個和第j+1個可以到達(dá)。你能幫助他找到最安全的路么？

Input

輸入數(shù)據(jù)為多組，到文件結(jié)束。對于每一組數(shù)據(jù)，第一行有一個數(shù)，為n 。n≤100;接下來有n行，第i行有i個數(shù)。代表第i個區(qū)間i個落腳點的危險值。所有數(shù)據(jù)均在int范圍內(nèi)。

Output

對于每組數(shù)據(jù)，輸出一行一個數(shù)，為答案。

Example Input

573 88 1 02 7 4 44 5 2 6 5Example Output
17Hint
 Author
lin
01 #include<stdio.h>
02 int min(int a, int b);
03 int main()
04 {
05     int i, n, j;
06     int a[111][111];
07     while(scanf("%d", &n) != EOF)
08     {
09         for(i = 1; i <= n; i++)
10         {
11             for(j = 1; j <= i; j++)
12                 scanf("%d", &a[i][j]);
13         }
14         for(i = n - 1; i >= 1; i--)
15         {
16             for(j = i + 1; j >= 1; j--)
17                 a[i][j] += min(a[i+1][j], a[i+1][j+1]);
18         }
19         printf("%d/n", a[1][1]);
20     }
21     return 0;
22 }
23 int min(int a, int b)
24 {
25     if(a > b) return b;
26     else return a;
27 }