NYOJ 372 巧克力的

时间:2023-03-08 17:10:52

巧克力

时间限制:4000 ms  |  内存限制:65535 KB
难度:2
描写叙述

布欧能够把人变成巧克力吃了来添加他的能量,也有可能降低。

如今布欧变了n*m个巧克力,并把巧克力排成一个n*m的矩形,如今布欧想选择一个子矩形,把这个子矩形吃了来添加他的能量,可他不知道选哪个才干使他的能量添加值p最大,布欧也能够选择一个都不吃。这样p
= 0。

如今布欧要你告诉他p的最大值,不然他就先把你变成巧克力吃了。

输入
第一行:一个整数T 代表測试个数,

接着T组測试数据。

对每组測试数据:

第一行:n m 两个整数

接着n行每行m个空格隔开的整数a(i,j)代表相应巧克力的能量值(注意能够是负数,吃了能量降低)



1<=n,m<=300

-1000<= a(i,j) <= 1000

输出
T行

每行一个整数 p
例子输入
3
3 3
1 -1 4
2 -2 3
3 -10 1
3 3
-1 -1 -1
-1 -1 -1
-1 -1 -1
3 3
1 1 -10
-1 1 -10
1 1 -10
例子输出
8
0
4
AC码:
#include<stdio.h>
int num[301][301];
int main()
{
int T,i,j,k,max=0,sum=0,n,m;
scanf("%d",&T);
for(i=0;i<=300;i++)
num[0][i]=0;
for(i=0;i<=300;i++)
num[i][0]=0;
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&num[i][j]);
num[i][j]+=num[i][j-1];
}
}
max=0;
for(i=1;i<=m;i++)
{
for(j=i;j<=m;j++)
{
sum=0;
for(k=1;k<=n;k++)
{
if(sum<0)
sum=num[k][j]-num[k][i-1];
else
sum+=num[k][j]-num[k][i-1];
if(sum>max)
max=sum;
}
}
}
printf("%d\n",max);
}
return 0;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。