NC16832. [NOI1997]最佳游览
描述
有一座旅游城，它的街道成网格状（如图）．其中东西向的街道是“风景线、两旁分布着许多景观：南北向的街道都是林萌道，两旁没有任何建筑物。由于游客众多，""" 风最线”被规定为单行道，游客在风景线上只能从西走到东，林丽道上则可以任意行走。
一名游客将到这座旅游城旅游。他根据自己对景观的喜好给所有的风景线打了分，分值是从-100到+100的整数，分值越大表示我们的旅游者越喜欢这条风最线上的景致。显然这位游客不可能给这座旅游城的所有风景线都打负分。
| -50 | -47 | -36 | -30 | -23 |
| 17 | -19 | 34 | -13 | -8 |
| -42 | -3 | 43 | 34 | -45 |
游客可以从旅游城的任一个十字路口开始游览，在任一个十字路口结束游览。我们的旅游者希望一路上游览的所有风最线的分值之和能够尽可能地大。请你写一个程序，帮助这位游客寻找一条最佳的游览路线。
输入描述
第一行是两个整数M和N，之间用一个空格符隔开，M表示旅游城南北向林萌道的段数，N表示东西向风景线的臣数，(1 ≤ M ≤ 100, 1 ≤ N ≤ 20000)。
接下来的M行依次给出了由北向南各条风景线的分值信息。每行有N个整数，依次表示了自西向东每段风景线的分值。同一行相邻两个数之间用一个空格隔开。
输出描述
只有一行，含一个整数，表示你的程序所找到的最佳游览路线的总分值。
示例1
输入:
3 5 50 –47 –36 –30 –23 17 –19 34 –13 –8 -42 –3 43 34 -45
输出:
84
C(clang11) 解法, 执行用时: 7ms, 内存消耗: 700K, 提交时间: 2022-12-30 14:10:56
#include <stdio.h>
int a[105][20005], maxa[20005];
long long f[20005], maxx = 0;
int max(long long a, long long b)
{
if (a > b)
return a;
return b;
}
int main()
{
int n, m;
scanf("%d%d", &m, &n);
n--;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n ; j++)
{
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= n; i++)
{
maxa[i]=-1e9;
for (int j = 1; j <= m; j++)
{
maxa[i] = max(maxa[i], a[j][i]);
}
}
for (int i = 1; i <= n; i++)
{
// printf("%d:", maxa[i]);
f[i] = max(f[i - 1] + maxa[i], maxa[i]);
maxx = max(maxx, f[i]);
// printf("%d\n", f[i]);
}
printf("%lld\n", maxx);
}
C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 636K, 提交时间: 2020-12-21 20:54:20
#include<bits/stdc++.h>
#define o(i,k,n)for(int i=k;i<=n;++i)
using namespace std;
int m,n;
int a[105][20005],arr[105],maxn[20005];
int findmax(int arr[])
{
sort(arr+1,arr+m+1);
return arr[m];
}
int main()
{
cin>>m>>n;
n--;
o(i,1,m)o(j,1,n)scanf("%d",&a[i][j]);
o(i,1,n)
{
o(j,1,m)
{
arr[j]=a[j][i];
}
maxn[i]=findmax(arr);
}
int ans=0;
o(i,1,n)
{
maxn[i]=max(maxn[i],maxn[i-1]+maxn[i]);
if(maxn[i]>ans)ans=maxn[i];
}
cout<<ans;
}