JZOJ 5838. 旅游路线最大子段和

Description

GZOI队员们到X镇游玩。X镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成m*n个区域，这些区域标从北到南、从西到东的坐标标识为从坐标 (1,1) 到坐标(m,n)。 GZOI队员们预先对这m*n个区域打分V(i，j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便游玩，队员们需要选定一个连续的区域集合作为活动范围。例如，如果他们选择了最西北的区域(m1，nl)和最东南(m2，n2)区域(m1<=m2，n1<=n2),那他们的活动范围是 {D(i，j)|m1<=i<=m2，n1<=j<=n2}，其游览总分则为这些活动范围的区域总分。 GZOI队员们希望他们活动范围内的区域的分值总和最大。你的任务是编写一个程序，求出他们的活动范围(m1，nl)，(m2，n2〉。

Input

输入第一行为整数m(1<=m<=200)，n(1<=n<=200)，用空格隔开下面为m行，每行有n列整数，其中第i行第j列的整数，代表V(i,j)，每个整数之间用空格隔开，每个整数的范围是 [-200000,200000]，输入数据保证这些整数中，至少存在一个正整数。

Output

输出只有一行，为最高的分值。

Sample Input

4 5
1 -2 3 -4 5
6 7 8 9 10
-11 12 13 14 -15
16 17 18 19 20

Sample Output

做法：最大子段和

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #define N 207
 5 #define LL long long
 6 #define rep(i,a,b) for(int i=a;i<=b;i++)
 7 #define max(a,b) (a)>(b)?(a):(b)
 8 using namespace std;
 9 int n,m,val[N][N];
10 LL f[N], Q[N][N], ans;
11 
12 void Init(){
13     scanf("%d%d",&n,&m);
14     rep(i,1,n)
15         rep(j,1,m){
16             scanf("%d",&val[i][j]);
17             Q[i][j]=Q[i-1][j]+val[i][j];
18         }
19 }
20 
21 void Get(int up,int down){
22     rep(i,1,m)
23         f[i]=Q[down+up][i]-Q[up-1][i];
24     LL sum=0;
25     rep(i,1,m){
26         if(sum+f[i]>0)    sum+=f[i],ans=max(ans,sum);
27         else sum=0;
28     }
29         
30 }
31 
32 void Work(){
33     rep(i,1,n)
34         rep(j,0,n-i)
35             Get(i,j);
36 }
37 
38 int main(){
39     Init();
40     Work();
41     printf("%lld",ans);
42 }

View Code