小鑫去爬山

秒速五厘米 2022-07-13 01:57 102阅读 0赞

#### Problem Description ####

马上就要放假了，小鑫打算去爬山。   
小鑫要去爬的这座山有n个海拔区间。为了清楚描述我们可以从上到下标号1到n。

第i个区间有i个落脚点，每一个落脚点都有一个危险值。

小鑫需要在第n个海拔区间挑选一个点向上爬，爬到第1个海拔区间（也就是山顶）。他必须规划一条路径，让危险值之和最小。这样才安全的。

并不是任意两个落脚点之间都可以相互到达。我们这样定义对于第i个（i<n）区间的第j个落脚点，只有第i+1个区间的第j个和第j+1个可以到达。

你能帮助他找到最安全的路么？

#### Input ####

输入数据为多组，到文件结束。

对于每一组数据，第一行有一个数，为n 。n≤100;

接下来有n行，第i行有i个数。代表第i个区间i个落脚点的危险值。

所有数据均在int范围内。

#### Output ####

对于每组数据，输出一行一个数，为答案。

#### Example Input ####

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

#### Example Output ####

17

\#include<stdio.h>  
int main()  
\{  
int n;  
int i,j;  
int a\[100\]\[100\]=\{0\};  
int d\[100\]\[100\]=\{0\};  
while(scanf("%d",&n)!=EOF)  
\{  
for(i=0;i<n;i++)  
\{  
for(j=0;j<=i;j++)  
\{  
scanf("%d",&a\[i\]\[j\]);  
\}  
\}  
for(i=0;i<n;i++)  
\{  
d\[n-1\]\[i\]=a\[n-1\]\[i\];  
\}  
for(i=n-1;i>=1;i--)  
\{  
for(j=0;j<i;j++)  
\{  
if(d\[i\]\[j\]<d\[i\]\[j+1\])  
\{  
d\[i-1\]\[j\]=d\[i\]\[j\]+a\[i-1\]\[j\];  
\}  
else  
\{  
d\[i-1\]\[j\]=d\[i\]\[j+1\]+a\[i-1\]\[j\];  
\}  
\}  
\}  
printf("%d\\n",d\[0\]\[0\]);  
\}  
return 0;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，102人围观）

还没有评论，来说两句吧...

相关阅读

相关懒虫小鑫

Problem Description 小鑫是个大懒虫，但是这一天妈妈要小鑫去山上搬些矿石去城里卖以补贴家用。小鑫十分的不开心。不开心归不开心，小鑫还是要做这件事情的。

约定不等于承诺〃/ 2022年07月13日 08:44/ 0 赞/ 166 阅读

相关小鑫去爬山

Problem Description 马上就要放假了，小鑫打算去爬山。小鑫要去爬的这座山有n个海拔区间。为了清楚描述我们可以从上到下标号1到n。第i个区间有

秒速五厘米/ 2022年07月13日 01:57/ 0 赞/ 103 阅读

相关小鑫去爬山

Problem Description 马上就要放假了，小鑫打算去爬山。小鑫要去爬的这座山有n个海拔区间。为了清楚描述我们可以从上到下标号1到n。第i个区间有

朴灿烈づ我的快乐病毒、/ 2022年07月12日 02:47/ 0 赞/ 335 阅读

相关商人小鑫

Problem Description 小鑫是个商人，当然商人最希望的就是多赚钱，小鑫也一样。这天，他来到了一个遥远的国度。那里有着n件商品，对于第i件商品需要付

港控/mmm°/ 2022年07月12日 02:45/ 0 赞/ 203 阅读

相关懒虫小鑫

Problem Description 小鑫是个大懒虫，但是这一天妈妈要小鑫去山上搬些矿石去城里卖以补贴家用。小鑫十分的不开心。不开心归不开心，小鑫还是要做这件事情的。

喜欢ヅ旅行/ 2022年07月12日 02:25/ 0 赞/ 177 阅读

相关懒虫小鑫

懒虫小鑫 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statistic][S

古城微笑少年丶/ 2022年06月17日 09:48/ 0 赞/ 200 阅读

相关小鑫去爬山

小鑫去爬山 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Problem

冷不防/ 2022年05月30日 10:10/ 0 赞/ 176 阅读

相关商人小鑫

商人小鑫 Problem Description 小鑫是个商人，当然商人最希望的就是多赚钱，小鑫也一样。这天，他来到了一个遥远的国度。那里有着n件商品，对于第i件商

墨蓝/ 2022年05月16日 13:11/ 0 赞/ 164 阅读

相关懒虫小鑫

懒虫小鑫 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description

一时失言乱红尘/ 2022年05月16日 13:09/ 0 赞/ 184 阅读

相关小鑫去爬山

Problem Description 马上就要放假了，小鑫打算去爬山。小鑫要去爬的这座山有n个海拔区间。为了清楚描述我们可以从上到下标号1到n。第i个区间有i

墨蓝/ 2022年05月16日 01:42/ 0 赞/ 119 阅读