巧克力
时间限制: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;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。