Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
话说LCINF信息组来到烟台参加夏令营。一天，大家提议出去游玩，来到了烟台最繁华的地方。由于他们对烟台不了解，怕迷了路，
所以，他们正焦急的想办法。这时，天上突然现身一个老人（这是真亊……），对我们说：“这片街道呈网状，其中东西向的街
道是旅游街，南北向的街道是绿化道。由于游客众多，旅游街被规定为单行道，只能由西向东走，而绿化道是双向通道，两个方
向都能通过，我在所有旅游街相邻两个路口之间打上了分值（-10000到10000之间），而在绿化道均没有打分。你们可以从任何
一个位置开始游览，从任何一个位置停止游览，但必须使得所经过分值的和最大。你们只要找到这样一条路径，我便出现带你们
离开这里（如图）。”。
说完，那位神秘的老人就消失了。信息组的同学们这才恍然大悟，于是就想办法，可是他们已经走了三个小时，还没有喝一口水
（苦啊！），他们已经筋疲力尽了。所以这个光荣而艰巨的任务就交给你了。帮助他们渡过难关吧！
【数据规模】
对于30%的数据 1<=m<=100 1<=n<=200
对于100%的数据 1<=m<=3000 1<=n<=500
【输入格式】
第一行两个整数m和n，表示m条横向街道，n个分值点。
接下来是一个m*n的矩阵。第I行第J列的数表示一个分值点。
【输出格式】
一行di表示完成的任务重要数总和。
Sample Input
3 5
-50 -47 36 -30 -23
17 -19 -34 -13 -8
-42 -3 -43 34 –45
Sample Output
84
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t061
【题意】
【题解】
每个位置的横向边选择分数最大的就好咯;
(因为竖向边是不计分的,所以选择哪个边是没有代价的);
然后从左往右看看在哪个位置停就好了;
对于全是负数的情况,我的程序判断是0;
【完整代码】
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 500+10;
int m,n;
int a[N],f[N];
int main()
{
//freopen("F:\rush.txt","r",stdin);
rei(m),rei(n);
rep1(i,1,n)
rei(a[i]);
rep1(i,2,m)
{
rep1(j,1,n)
{
int x;
rei(x);
a[j] = max(a[j],x);
}
}
f[0] = 0,f[1] = a[1];
rep1(i,2,n)
f[i] = f[i-1]+a[i];
int t = f[0];
rep1(i,1,n)
t = max(t,f[i]);
printf("%d
",t);
return 0;
}