开始看到这题以为是二维线段树，但是二维的线段树从来没写过也不知道怎么写，昨天晚上突来灵感，可以用复杂度为c2的一个方法，每次比较两个矩阵是否相交，然后更新矩阵的值，速度很快！zoj月赛ac这题的人大部分都是这种方法吧，内存才200k。。。法克，我早该想到！！！
#include<iostream>#include<vector>#include<cstring>#include<cstdio>#include<iomanip>#include<algorithm>#include<cassert>using namespace std;const int maxn = 1011;struct zz{int x1,y1;int x2,y2;int h;}zx[maxn];int x,y,a,b,h;int n,m,c,temp,ans;bool yes(int i,int j){if(zx[i].y2 < zx[j].y1 || zx[i].y1 > zx[j].y2 || zx[i].x2 < zx[j].x1 || zx[i].x1 > zx[j].x2){return false;}return true;}int main(){while(scanf("%d%d%d",&n,&m,&c)==3){ans = 0;for(int i=1;i<=c;i++){// cin>>a>>b>>h>>x>>y;scanf("%d%d%d%d%d",&a,&b,&h,&x,&y);zx[i].x1 = x;zx[i].y1 = y;zx[i].x2 = x + a - 1;zx[i].y2 = y + b - 1;temp = h;for(int j=1;j<i;j++){if(yes(i,j)){if( h + zx[j].h > temp ){temp = h + zx[j].h;}}}zx[i].h = temp;if(temp > ans){ans = temp;}}printf("%d\n",ans);}return 0;}
