最佳游览（noi1997）

题目

有一座旅游城，它的街道成网格状（如图）．其中东西向的街道是“风景线、两旁分布着许多景观：南北向的街道都是林萌道，两旁没有任何建筑物。由于游客众多，""" 风最线”被规定为单行道，游客在风景线上只能从西走到东，林萌道上则可以任意行走。
一名游客将到这座旅游城旅游。他根据自己对景观的喜好给所有的风景线打了分，分值是从-100到+100的整数，分值越大表示我们的旅游者越喜欢这条风最线上的景致。显然这位游客不可能给这座旅游城的所有风景线都打负分。

图1

游客可以从旅游城的任一个十字路口开始游览，在任一个十字路口结束游览。我们的旅游者希望一路上游览的所有风最线的分值之和能够尽可能地大。请你写一个程序，帮助这位游客寻找一条最佳的游览路线。

输入输出

输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示旅游城南北向林萌道的段数，N表示东西向风景线的条数，l<=M<=100，1<=N<=20001。接下来的M行依次给出了由北向南各条风景线的分值信息。每行有N-1个整数，依次表示了自西向东每段风景线的分值。同一行相邻两个数之间用一个空格隔开。输出文件是OUTPUT.TXT。文件只有一行，含一个整数，表示你的程序所找到的最佳游览路线的总分值。

样例

INPUT.TXT
3 6
-50 –47 36 –30 –23
17 –19 -34 –13 –8
-42 –3 -43 34 -45

OUTPUT.TXT
84

分析

游客在风景线上只能从西走到东，林萌道上则可以任意行走。

由题目中的这句话我们可以知道问题的本质是对每一列数据求最大值后，求出最大连续子序列和就可以得出结果。

代码如下

#include<stdio.h>
#include<stdlib.h>
int a[100][20001],b[20001],sum[20001];
int main()
{
    int h,l;
    scanf("%d%d",&h,&l);
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<l;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
//  求解每列最大值 
    for(int j=1;j<l;j++)
    {
        b[j]=-101; 
    
        for(int i=1;i<=h;i++)
        {
            if(a[i][j]>b[j])
            {
                b[j]=a[i][j];
            }
        }
        printf("%d  ",b[j]);
    }

//  求解最大连续子序列和 
    b[0] = 0;
    int ans = b[1];
    for(int i = 1; i < l; i++) {
        if(b[i - 1] > 0) b[i] += b[i - 1];
        else b[i] += 0;
        if(b[i] > ans) ans = b[i];
    }

    printf("%d\n", ans);

    return 0;
}

欢迎关注微信公众号 待定程序猿 一起学习进步

待定程序猿