首页 > 代码库 > [USACO] 铺放矩形块 题解
[USACO] 铺放矩形块 题解
题目大意:
给定4个矩形块,找出一个最小的封闭矩形将这4个矩形块放入,但不得相互重叠。所谓最小矩形指该矩形面积最小。
思路:
枚举矩形的安放顺序,再按照题目所给的图判断即可,主要要想到枚举。
代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int i,n,sum=10009,p[5],q[5],a[5],b[5]; 4 struct data { int x,y; }ans[10000]; 5 bool used[5]; 6 7 bool cmp(data a,data b) { return a.x<b.x; } 8 9 void pd(int l,int r) 10 { 11 if (l*r<sum) 12 { 13 sum=l*r,ans[n=1].x=l,ans[1].y=r; 14 if (l>r) swap(ans[1].x,ans[1].y); 15 return; 16 } 17 if (l*r==sum) 18 { 19 ans[++n].x=l,ans[n].y=r; 20 if (l>r) swap(ans[n].x,ans[n].y); 21 } 22 } 23 24 void dfs(int k) 25 { 26 if (k>4) 27 { 28 int l=0,r=0,i; 29 for (i=1;i<5;i++) l=max(l,p[i]),r+=q[i]; 30 pd(l,r);//1 31 for (l=r=0,i=1;i<4;i++) l=max(l,p[i]),r+=q[i]; 32 pd(l+p[4],max(r,q[4]));//2 33 l=max(p[1],p[2])+p[3],r=max(q[1]+q[2],q[3]); 34 pd(max(l,p[4]),r+q[4]);//3 35 l=max(p[1],p[2]),r=max(q[3],q[4]); 36 pd(l+p[3]+p[4],max(r,q[1]+q[2]));//5 37 l=max(p[1]+p[2],p[3]+p[4]); 38 if (q[1]>=q[2]) 39 if (q[4]>q[3]) pd(l,q[1]+q[4]); 40 else 41 if (p[1]+p[3]<=l) pd(l,max(q[1]+q[4],q[2]+q[3]));//6 42 return; 43 } 44 for (int i=1;i<5;i++) 45 if (!used[i]) 46 { 47 used[i]=1; 48 p[k]=a[i],q[k]=b[i],dfs(k+1); 49 p[k]=b[i],q[k]=a[i],dfs(k+1); 50 used[i]=0; 51 } 52 } 53 54 int main() 55 { 56 for (i=1;i<5;i++) scanf("%d%d",&a[i],&b[i]); 57 dfs(1),sort(ans+1,ans+n+1,cmp),printf("%d\n",sum); 58 printf("%d %d\n",ans[1].x,ans[1].y); 59 for (i=2;i<=n;i++) 60 if (ans[i].x!=ans[i-1].x) printf("%d %d\n",ans[i].x,ans[i].y); 61 return 0; 62 }
[USACO] 铺放矩形块 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。