首页 > 代码库 > UVa 10755 Garbage Heap

UVa 10755 Garbage Heap

2024-07-16 06:36:28   219人阅读

三维的形式下的最大子段问题

既然二维可以压缩成一维的情况，那么同样的，三维也可以压缩成一维转化成最大子段问题

枚举y和z的边界，压缩后在x轴上求最大子段，用ans记录最大值

时间复杂度是O(n^5)，由于数据不算太大，所以不会超时

 

一直WA，一直WA，Orz

后来终于发现是输出格式的问题，每个输出之间都要加一个换行符，换行啊换行！你坑死窝了

为何反馈信息是WA而不是PE，真是误导人啊。=_=!!

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 30; 9 long long cube[maxn][maxn][maxn], sum[maxn][maxn][maxn], a[maxn];10 const long long INF = 1LL << 60;11 12 int main(void)13 {14     #ifdef LOCAL15         freopen("10755in.txt", "r", stdin);16     #endif17 18     int T;19     scanf("%d", &T);20     while(T--)21     {22         int x, y, z;23         int i, j, k;24         scanf("%d%d%d", &x, &y, &z);25         for(i = 1; i <= x; ++i)26             for(j = 1; j <= y; ++j)27                 for(k = 1; k <= z; ++k)28                     scanf("%lld", &cube[i][j][k]);29         memset(sum, 0, sizeof(sum));30         for(i = 1; i <= x; ++i)31             for(j = 1; j <= y; ++j)32                 for(k = 1; k <= z; ++k)33                     sum[i][j][k] = sum[i][j-1][k] + sum[i][j][k-1] - sum[i][j-1][k-1] + cube[i][j][k];34 35         long long ans = -INF;36         for(int i1 = 1; i1 <= y; ++i1)37             for(int i2 = i1; i2 <= y; ++i2)38                 for(int j1 = 1; j1 <= z; ++j1)39                     for(int j2 = j1; j2 <= z; ++j2)40                     {41                         for(k = 1; k <= x; ++k)42                             a[k] = sum[k][i2][j2] - sum[k][i1-1][j2] - sum[k][i2][j1-1] + sum[k][i1-1][j1-1];43 44                         ans = max(a[1], ans);45                         for(k = 2; k <= x; ++k)46                         {47                             a[k] = max(a[k], a[k] + a[k-1]);48                             ans = max(ans, a[k]);49                         }50                     }51 52         printf("%lld\n", ans);53         if(T)54             printf("\n");55     }56     return 0;57 }
萌萌的代码君

 


联系
我们