题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=1696
和二维的最大子矩阵的思想是一样的,只是变成了三维的。
枚举层数的上下界, 然后把上下界之间的所有层“压缩”成一层,在这“一层”上用二维的方法再计算。
注意用long long
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cctype>
using namespace std;
typedef long long int64 ;
const int MAXN = 25;
int A, B, C;
int64 cube[MAXN][MAXN][MAXN];
inline int64 read_int64(){
char ch = getchar();
while(!isdigit(ch) && ch!='-') ch=getchar();
bool neg = false;
if(ch == '-') neg=true, ch=getchar();
int64 ans=0;
while(isdigit(ch)){
ans = ans*10+ch-'0';
ch = getchar();
}
if(neg) return -ans;
return ans;
}
inline void input(){
scanf("%d%d%d", &A,&B,&C);
memset(cube, 0, sizeof(cube));
for(int k=1; k<=A; ++k){
for(int i=1; i<=B; ++i){
for(int j=1; j<=C; ++j){
cube[k][i][j] = read_int64();
cube[k][i][j] += cube[k][i][j-1]-cube[k][i-1][j-1]+cube[k][i-1][j]
- (cube[k-1][i][j-1]-cube[k-1][i-1][j-1]+cube[k-1][i-1][j])
+ cube[k-1][i][j];
} //列
} //行
}//层
}
int64 solve(){
// 枚举层数的上下界
int64 ans = -2147483647-1;
for(int down=0; down<A; ++down){
for(int up=down+1; up<=A; ++up){
// 枚举层上的“行”
for(int d=0; d<B; ++d){
for(int u=d+1; u<=B; ++u){
int64 minx = 0;
for(int k=1; k<=C; ++k){
int64 sum = (cube[up][u][k]-cube[down][u][k])
- (cube[up][d][k]-cube[down][d][k]);
ans = max(ans, sum-minx);
if(sum < minx) minx=sum;
}
}
}
}
}
return ans;
}
int main(){
int nCase;
scanf("%d", &nCase);
while(nCase--){
input();
cout << solve() << endl;
if(nCase) putchar('\n');
}
return 0;
}
分享到:
相关推荐
The Java Platform, Standard Edition HotSpot Virtual Machine Garbage Collection Tuning Guide describes the garbage collection methods included in the Java HotSpot Virtual Machine (Java HotSpot VM) and ...
JDK12-hotspot-virtual-machine-garbage-collection-tuning-guide
JDK15-hotspot-virtual-machine-garbage-collection-tuning-guide
JDK11-hotspot-virtual-machine-garbage-collection-tuning-guide
JDK16-hotspot-virtual-machine-garbage-collection-tuning-guide
JDK17-hotspot-virtual-machine-garbage-collection-tuning-guide
JDK18-hotspot-virtual-machine-garbage-collection-tuning-guide
JDK19-hotspot-virtual-machine-garbage-collection-tuning-guide
jdk20-hotspot-virtual-machine-garbage-collection-tuning-guide Java Platform, Standard Edition HotSpot Virtual Machine Garbage Collection Tuning Guide-58
藏经阁-Garbage In,Garbage Out
InfoQ的关于JVM GC的学习资料,对于深入学习JVM的GC机制很有帮助
Tiny-Garbage是围绕关系数据库(sqlite,mysql ...)设计的,非常适合索引小型网络Tiny-Garbage2是围绕非关系数据库(MongoDB)设计的,能够扩展到数十万个文件和目录的索引编制,而不会造成重大性能损失Tiny-...
libunwind - a platform-independent unwind library.FIXME for AArch64.
Java 1.5 jvm 虚拟机调优技术
Garbage-First is a server-style garbage collector, targeted for multi-processors with large memories, that meets a soft real-time goal with high probability, while achieving high throughput. Whole-...
系统级编程课程的垃圾回收实验 有代码与文档说明
G1垃圾回收器论文。 Garbage-First Garbage Collection October 24-25, 2004
Java 垃圾回收经典手册,讲得特别清楚,非常推荐!
$ composer require spinen/laravel-garbage-man 对于> = Laravel 5.5,安装完成 该软件包使用Laravel 5的自动注册功能。 从1.x升级到2.x 从Laravel 5.8(并在5.4中弃用)开始,出于对dispatch()支持而删除了调度...
npm install useless-garbage -g --save --save-dev 我们建议在上面的示例中包括所有标志。 仅-g将适用,这使得其余部分无用。 正是我们想要的方式。 例子 无用垃圾提供了大量无用的功能。 这里只是几个例子。 ...