Description
在一座山上,有很多很多珠寶,它們散落在山底通往山頂的每條道路上,不同道路上的珠寶的數目也各不相同.下圖為一張藏寶地圖:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
”奪寶奇兵”從山下出發,到達山頂,如何選路才能得到最多的珠寶呢?在上圖所示例子中,按照5-> 7-> 8-> 3-> 7的順序,將得到最大值30，
Input
第一行正整數N(100> =N> 1),表示山的高度
接下來有N行非負整數,第i行有i個整數(1< =i< =N),表示山的第i層上從左到右每條路上的珠寶數目
Output
一個整數,表示從山底到山頂的所能得到的珠寶的最大數目.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
思路：
很經典的動態規劃題，
假設為N=3；
分別為
7 ---------i=1； 3 8 ----------i=2； 8 1 0 ------------i=3；
那么 從i=3---->i=2；
想要到達3，可選擇2條路 一個從8上去， 一個從1上去，那么選擇二者之間最大的那個并且進行覆寫，
同理想要到達8也一樣，
i=2變成
7 -------i=1；
11 9 -------i=2；
那么從i=2------->i=1；
選擇11
最終i=1 的那條路為 18；
至此結束；
即需要兩個陣列，
一個data存數字山，另一個updata進行覆寫；
并且覆寫為：updata[i]=max（updata[i],updata[i+1]）+data[i][j]
上代碼：
#include<iostream>
using namespace std;
int main(void)
{
int updata[105];
int data[105][105];
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>data[i][j]; //存數字山
for(int i=1;i<=n;i++)
updata[i]=data[n][i]; //將最后一行的數字山賦值給updata
for(int i=n-1;i>=1;i--) //進行n-1次覆寫行操作
for(int j=1;j<=i;j++){ //進行i次覆寫操作
updata[j]=max(updata[j],updata[j+1])+data[i] [j]; //當然要加上目前將要覆寫的數字值
}
cout<<updata[1]<<endl; //到最后登上山頂也就覆寫的只剩下最后一個最優資料了
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/232099.html
標籤：其他