有一個(gè)數(shù)字三角形，共$n$行，依次編號(hào)為第一行，第二行至第$n$行。其中第$i$行有$i$個(gè)數(shù)字，位置依次記為$(i,1),(i,2)$到$(i,i)$。
現(xiàn)在從第$n$層的第一個(gè)位置出發(fā)（即$(n,1)$），每一步移到相鄰的，且行編號(hào)小于或等于當(dāng)前行編號(hào)的一個(gè)位置中，直到$(1,1)$結(jié)束，在不重復(fù)經(jīng)過任何位置的情形下，路過的所有位置（包括端點(diǎn)）的對(duì)應(yīng)數(shù)字之和最小。

下面詳細(xì)定義相鄰關(guān)系。
同一層內(nèi)連續(xù)的兩個(gè)位置相鄰，特別的有每一層第一個(gè)位置與最后一個(gè)位置相鄰。
對(duì)于位置$(i,j)$，它與$(i?1,j?1)$以及$(i?1,j)$相鄰，特別的$(i,1)$與$(i?1,i?1)$相鄰，且$(i,i)$與$(i?1,1)$相鄰。

格式

輸入格式

第一行有一個(gè)數(shù)n（2<=n<=1000），表示山的高度。

從第二行至第n+1行，第i+1行有i個(gè)數(shù)，每個(gè)數(shù)表示晴天小豬在這一段山路上需要爬的時(shí)間。

輸出格式

一個(gè)數(shù)，即晴天小豬所需要的最短時(shí)間。

樣例1

樣例輸入1

5 1 2 3 4 5 6 10 1 7 8 1 1 4 5 6 Copy

樣例輸出1

10 Copy

限制

各個(gè)測(cè)試點(diǎn)1s

提示

在山的兩側(cè)的走法略有特殊，請(qǐng)自己模擬一下，開始我自己都弄錯(cuò)了……

思路：

輸入的是一個(gè)n行，第i行有i個(gè)數(shù)的數(shù)字三角形。個(gè)人比較喜歡舉個(gè)具體的例子進(jìn)行分析。如下：

1

2? ? 3

4? ?5? ?6

7? ?8? ?9? ?10

11? ?12? ?13? ?14? ?15

為一個(gè)5行的數(shù)字三角形。

其可能行走的路線是，向左，向右，斜向上，斜向下，而特殊點(diǎn)（即邊界點(diǎn)）對(duì)應(yīng)的斜上方可以到上一行的另一邊。

例如：5可以到4，6，2，3；11可以到12，15，7，10；

一般化則為a[i][j]可以向a[i][j-1],a[i][j+1],a[i-1][j-1],a[i-1][j]位置走。

臨界處：a[i][1]可以向a[i][2],a[i][i],a[i-1][1],a[i-1][i-1]位置走；a[i][i]同理。

我們從上往下推，如果走到a[i][j]此時(shí)是最短的，那么之前的路程都是最短的。

所以我們可以以頂點(diǎn)為起點(diǎn)，計(jì)算到達(dá)底部各點(diǎn)的最短距離。

#include <iostream>using namespace std;int main() {int num;cin>>num;int ang[num+1][num+1];int f[num+1][num+1];for(int i=1;i<=num;i++)for(int j=1;j<=i;j++)cin>>ang[i][j];f[1][1]=ang[1][1]; //以此為起點(diǎn)for(int i=2;i<=num;i++){for(int j=2;j<i;j++)f[i][j]=min(f[i-1][j-1],f[i-1][j])+ang[i][j]; //計(jì)算上一層到這一層的最短距離f[i][1]=min(f[i-1][i-1],f[i-1][1])+ang[i][1]; f[i][i]=min(f[i-1][i-1],f[i-1][1])+ang[i][i]; //剔除特別點(diǎn)for(int j=2;j<=i;j++)f[i][j]=min(f[i][j],f[i][j-1]+ang[i][j]); //從左到右計(jì)算同一層最短距離f[i][1]=min(f[i][1],f[i][i]+ang[i][1]);for(int j=i-1;j>=1;j--)f[i][j]=min(f[i][j],f[i][j+1]+ang[i][j]);f[i][i]=min(f[i][i],f[i][1]+ang[i][i]); //從右到左計(jì)算同一層最短距離}cout<<f[num][1];return 0; }

總結(jié)

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

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