$$最佳瀏覽路線問題$$

題目描述

某旅游區(qū)的街道成網(wǎng)格狀（見圖），其中東西向的街道都是旅游街，南北向的街道都是林蔭道。由于游客眾多，旅游街被規(guī)定為單行道。游客在旅游街上只能從西向東走，在林蔭道上既可以由南向北走，也可以從北向南走。阿隆想到這個旅游區(qū)游玩。他的好友阿福給了他一些建議，用分值表示所有旅游街相鄰兩個路口之間的道路值得瀏覽得程度，分值從-１００到１００的整數(shù)，所有林蔭道不打分。所有分值不可能全是負(fù)值。

例如下圖是被打過分的某旅游區(qū)的街道圖：

阿隆可以從任一路口開始瀏覽，在任一路口結(jié)束瀏覽。請你寫一個程序，幫助阿隆尋找一條最佳的瀏覽路線，使得這條路線的所有分值總和最大。

輸入

第一行是兩個整數(shù)M和N，之間用一個空格符隔開，M表示有多少條旅游街（1≤M≤100），N表示有多少條林蔭道（1≤N≤20000）。接下里的M行依次給出了由北向南每條旅游街的分值信息。每行有N-1個整數(shù)，依次表示了自西向東旅游街每一小段的分值。同一行相鄰兩個數(shù)之間用一個空格隔開。

輸出

只有一行，是一個整數(shù)，表示你的程序找到的最佳瀏覽路線的總分值。

輸入樣例

3 6

-50 –47 36 –30 –23

17 –19 -34 –43 –8

-42 –3 -43 34 -45

輸出樣例

84

解題思路

這道題就是一道貪心題，它上和下不會加這個數(shù)，只有向右才要加這個數(shù)，只要求出每一列的最大數(shù)，再將這些數(shù)用最大連續(xù)數(shù)列的方法做，就可得出結(jié)果

#include<cstdio> #include<iostream> using namespace std; int n,m,a,sum,num,b[20001]; int main() {scanf("%d%d",&n,&m);m--;//每行有n-1個整數(shù)for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){scanf("%d",&a);if (i==1) b[j]=a;//如果直接用max，在負(fù)數(shù)的情況下就會不加else b[j]=max(b[j],a);//求每一列最大的}for (int i=1;i<=m;i++){num+=b[i];//最大連續(xù)數(shù)列的方法if (num<0)num=0;if (num>sum)sum=num;}printf("%d",sum); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【贪心】最佳浏览路线问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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