Posted on 2012-03-19 13:36
C小加 阅读(434)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
一直认为是二维线段树，看了解题报告后居然是水题。
最多1000个矩形。每次扫描矩形与之前的矩形是否相交，在相交的矩形中找到一个最大的值max，让这个max加上h就是这次矩形的值。每次向回扫描一遍，最高也就1000*1000的时间，1s内绝对没问题。
#include<iostream>
#include<cstdio>
using namespace std;
typedef struct
{
int x1,y1,x2,y2,_max;
}Matrix;
Matrix matrix[1003];
bool cover(int i,int j)//是否相交
{
if(matrix[i].x1>=matrix[j].x2||matrix[j].x1>=matrix[i].x2) return false;
if(matrix[i].y1>=matrix[j].y2||matrix[j].y1>=matrix[i].y2) return false;
return true;
}
int main()
{
int N,M,C;
while(scanf("%d %d %d",&N,&M,&C)!=EOF)
{
int ans=0;
int a,b,h,x,y;
for(int i=0;i<C;i++)
{
int tmax=0;
scanf("%d %d %d %d %d",&a,&b,&h,&x,&y);
matrix[i].x1=x;
matrix[i].y1=y;
matrix[i].x2=x+a;
matrix[i].y2=y+b;
for(int j=i-1;j>=0;j--)
{
if(cover(i,j))
{
tmax=max(tmax,matrix[j]._max);
}
}
matrix[i]._max=tmax+h;
ans=max(ans,matrix[i]._max);
}
printf("%d\n",ans);
}
return 0;
}