Posted on 2012-03-19 13:36
C小加 閱讀(471)
評論(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;
}