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

5838. 旅游路线

Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits

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

做法：最大子段和

代码如下：

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #define N 207

 #define LL long long

 #define rep(i,a,b) for(int i=a;i<=b;i++)

 #define max(a,b) (a)>(b)?(a):(b)

 using namespace std;

 int n,m,val[N][N];

 LL f[N], Q[N][N], ans;

 void Init(){

     scanf("%d%d",&n,&m);

     rep(i,,n)

         rep(j,,m){

             scanf("%d",&val[i][j]);

             Q[i][j]=Q[i-][j]+val[i][j];

         }

 }

 void Get(int up,int down){

     rep(i,,m)

         f[i]=Q[down+up][i]-Q[up-][i];

     LL sum=;

     rep(i,,m){

         if(sum+f[i]>)    sum+=f[i],ans=max(ans,sum);

         else sum=;

     }

 }

 void Work(){

     rep(i,,n)

         rep(j,,n-i)

             Get(i,j);

 }

 int main(){

     Init();

     Work();

     printf("%lld",ans);

 }

巴特西

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

5838. 旅游路线

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

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

5838. 旅游路线

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

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