题目大意：有一些矩形，这些矩形有单位权值，求一种覆盖方式，得最大权值，后面的矩形会覆盖前面的矩形。
题目思路：矩形切割，这个题很适合用矩形切割，矩形很少，复杂度不高。
[cpp] #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define uint unsigned __int64 #define M 5000 struct node { int p1[2],p2[2],value; bool operator<(const node a) const { return value } }a[M],b[30],now; int total; int judge(node a,node b) { for(int i=0;i<2;i++) { if(a.p2[i]<=b.p1[i]||a.p1[i]>=b.p2[i]) return 0; } return 1; } void cut(node tmp) { int k1,k2; for(int i=0;i<2;i++) { k1=max(tmp.p1[i],now.p1[i]); k2=min(tmp.p2[i],now.p2[i]); if(tmp.p1[i] { a[++total]=tmp; a[total].p2[i]=k1; } if(tmp.p2[i]>k2) { a[++total]=tmp; a[total].p1[i]=k2; } tmp.p1[i]=k1; tmp.p2[i]=k2; } } int main() { int t,n,i,j,count=1; long long sum; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d%d%d%d",&b[i].p1[0],&b[i].p1[1],&b[i].p2[0],&b[i].p2[1],&b[i].value); } sort(b+1,b+n+1); total=0; for(i=1;i<=n;i++) { now=b[i]; for(j=total;j>=1;j--) { if(judge(now,a[j])) { cut(a[j]); a[j]=a[total--]; } } a[++total]=now; } sum=0; for(i=1;i<=total;i++) { sum+=(long long)a[i].value*(a[i].p2[0]-a[i].p1[0])*(a[i].p2[1]-a[i].p1[1]); } printf("Case %d: %I64d\n",count++,sum); } }