首页 > > 程序设计 > C/C++ >

UVA 10755 Garbage Heap

2018-06-17 21:46:32来源：未知阅读 ()

题目大意就是求一个立方体的最大子立方体，权值有正有负有0，边长不超过20。

一个n维的最大子n维的是不是很眼熟？看看一维的怎么做。

一维？最大子段和，O(n)可做。

记S[i]表示前缀和，则任意一个子段和都可以表示成S[r]-S[l-1]。

对于一个点i，求以i结尾的最大子段和，就是要S[i]-S[j]最大(j<i)

所以就是要S[j]最小，这个好啊，记录一下就可以了，复杂度化为O(n)。

二维？最大子矩阵？

枚举上下界，把它拍扁，每次加的一列就可以看成一个数。

用二维前缀和优化，化为一维问题处理。复杂度O(n^3)。

三维？最大子立方体？

是不是感觉到我要说什么了……

枚举上下左右界，把它拍扁，每次加的一个矩形就可以看成一个数。

用二维前缀和优化，化为一维问题处理。复杂度O(n^5)。

这样就可以过了。

很容易推广到更高维，不过维越高点越少，好像没什么实际价值。

还有就是TM的输出格式的问题，WA了半个上午，和这个小伙子一起WA了一整版。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "10755"
using namespace std;

const int N = 21;
const LL Inf = 1ll<<60;
LL A,B,C,Y[N][N][N],Ans;

inline LL gi(){
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline LL MAX(LL a,LL b){
  return a>b?a:b;
}

inline LL MIN(LL a,LL b){
  return a<b?a:b;
}

inline void solve(){
  LL A=gi(),B=gi(),C=gi();Ans=-Inf;
  memset(Y,0,sizeof(Y));
  for(int i=1;i<=A;++i)
    for(int j=1;j<=B;++j)
      for(int k=1;k<=C;++k)
        Y[i][j][k]=gi()+Y[i-1][j][k]+Y[i][j-1][k]-Y[i-1][j-1][k];
  for(int lef=1;lef<=A;++lef)
    for(int rig=lef;rig<=A;++rig)
      for(int dow=1;dow<=B;++dow)
        for(int up=dow;up<=B;++up){
          LL Sum=0,Min=0;
          for(int fro=1;fro<=C;++fro){
            Sum=Sum+Y[rig][up][fro]-Y[rig][dow-1][fro]-Y[lef-1][up][fro]+Y[lef-1][dow-1][fro];
            Ans=MAX(Ans,Sum-Min);
            Min=MIN(Min,Sum);
          }
        }
  printf("%lld\n",Ans);
}

int main()
{
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  int Case=gi();
  for(int t=1;t<=Case;++t){
    solve();
    if(t^Case)printf("\n");
  }
  return 0;
}