Posted on 2012-03-19 13:36
C小加 閱讀(475)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告
一直認(rèn)為是二維線(xiàn)段樹(shù)，看了解題報(bào)告后居然是水題。
最多1000個(gè)矩形。每次掃描矩形與之前的矩形是否相交，在相交的矩形中找到一個(gè)最大的值max，讓這個(gè)max加上h就是這次矩形的值。每次向回掃描一遍，最高也就1000*1000的時(shí)間，1s內(nèi)絕對(duì)沒(méi)問(wèn)題。
#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;
}