NYOJ 372 巧克力

巧克力

时间限制：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];elsesum+=num[k][j]-num[k][i-1];if(sum>max)max=sum;}}}printf("%d\n",max);}return 0; }

总结

以上是生活随笔为你收集整理的NYOJ 372 巧克力的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。