題目

有如下所示的數(shù)塔，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點(diǎn)，則經(jīng)過的結(jié)點(diǎn)的數(shù)字之和最大是多少？并輸出最大和的路徑。

Input

輸入數(shù)據(jù)首先包括一個(gè)整數(shù)C,表示測試實(shí)例的個(gè)數(shù)，每個(gè)測試實(shí)例的第一行是一個(gè)整數(shù)N(1 <= N <= 100)，表示數(shù)塔的高度，接下來用N行數(shù)字表示數(shù)塔，其中第i行有個(gè)i個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間[0,99]內(nèi)。

Output

對(duì)于每個(gè)測試實(shí)例，輸出兩行。
第一行：輸入最大和。
第二行：如果最大和的路徑是唯一的，輸出其路徑（詳細(xì)格式見樣例輸出），否則輸出” There are several solutions!”

Sample Input

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

Sample Output

30
(0, 0) -> (1, 0) -> (2, 0) -> (3, 1) -> (4, 1)
3
There are several solutions!

Hint

不要用cin 和 cout，否則會(huì)超時(shí)(⊙_⊙)

代碼

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() {int a[101][101],d[101][101],map[101][101];int n,m;while(~scanf("%d",&n)){while(n--){memset(map,0,sizeof(map));scanf("%d",&m);for(int i=0;i<m;i++)for(int j=0;j<i+1;j++){scanf("%d",&d[i][j]);a[i][j] = d[i][j];}for(int i=m-2;i>=0;i--)for(int j=0;j<=i;j++)a[i][j]+=max(a[i+1][j],a[i+1][j+1]);printf("%d\n",a[0][0]);int i=0,j=0,c=0;while(j < m-1 && i < m-1){if((a[i][j]-d[i][j]) == a[i+1][j]&&(a[i][j]-d[i][j]) == a[i+1][j+1]){c = 1;break;}else{if(a[i+1][j] < a[i+1][j+1]) j++;}i++;map[i][j] = 1;}if(c) printf("There are several solutions!\n");else{printf("(0, 0)");j = 0;for(int i=1;i<m;i++){if(map[i][j] == 1) printf(" -> (%d, %d)",i,j);else printf(" -> (%d, %d)",i,++j);}printf("\n");}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数数塔 NBUT - 1083的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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