程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3634 City Planning

hdu 3634 City Planning

編輯:C++入門知識

題目大意:有一些矩形,這些矩形有單位權值,求一種覆蓋方式,得最大權值,後面的矩形會覆蓋前面的矩形。

題目思路:矩形切割,這個題很適合用矩形切割,矩形很少,復雜度不高。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
#include<math.h> 
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.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]<k1) 
                { 
                        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); 
        } 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved