首页 > 代码库 > Uva10755
Uva10755
在题中的A*B*C的矩形中，当确定X1，X2,Y1，Y2时，1->z的子矩形的和为
sum[x2][y2][1] -(sum[x1-1][y2][1] + sum[x2][y1-1][1] -sum[x1-1][y1-1][1] + sum[x2][y2][z+1] - sum[x1-1][y2][z+1] -sum[x2][y1-1][z+1] + sum[x1-1][y1-1][z+1]);
sum[x][y][z]指的是，以(x,y,z)为右下角的矩形的和
sum[x][y][z]的递推公式为 sum[k][j][i] = (sum[k-1][j][i] + sum[k][j-1][i] -sum[k-1][j-1][i] + sum[k][j][i+1] - sum[k-1][j][i+1] -sum[k][j-1][i+1] + sum[k-1][j-1][i+1] + d[k][j][i]);
本题最后结果可能会很大，所以ans的初值要赋值为最小的longlong
#include<bits/stdc++.h>#define inf 0x3f3f3f3fconst int maxn=20;using namespace std;typedef long long ll;int t;int a,b,c;ll d[maxn+10][maxn+10][maxn+10];ll sum[maxn+10][maxn+10][maxn+10];int main(){ scanf("%d",&t); while(t--){ memset(d, 0 ,sizeof(d)); memset(sum,0,sizeof(sum)); scanf("%d%d%d",&a,&b,&c); for(int i = 1; i <= a; i++){ for(int j = 1; j <= b; ++j){ for(int k = 1; k <= c; ++k){ scanf("%lld",&d[i][j][k]); } } } for(int i = c; i >= 1; --i){ for(int j = 1; j <= b; ++j){ for(int k = 1; k <= a; ++k){ sum[k][j][i] = (sum[k-1][j][i] + sum[k][j-1][i] - sum[k-1][j-1][i] + sum[k][j][i+1] - sum[k-1][j][i+1] - sum[k][j-1][i+1] + sum[k-1][j-1][i+1] + d[k][j][i]); } } } ll ans = -(ll)((1LL)<<63); for(int x1 = 1; x1 <= a; ++x1){ for(int x2 = x1; x2 <= a; ++x2){ for(int y1 = 1; y1 <= b; ++y1){ for(int y2 = y1; y2 <= b; ++y2){ ll min_sumz = 0; for(int z = 1; z <= c; ++z){ ll temp = sum[x2][y2][1] - (sum[x1-1][y2][1] + sum[x2][y1-1][1] - sum[x1-1][y1-1][1] + sum[x2][y2][z+1] - sum[x1-1][y2][z+1] - sum[x2][y1-1][z+1] + sum[x1-1][y1-1][z+1]); ans = max(ans, temp - min_sumz); min_sumz = min(min_sumz, temp); } } } } } printf("%lld\n",ans); if(t){ printf("\n"); } } return 0;}
Uva10755
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。