当前位置: 代码迷 >> 综合 >> [U]Packing Rectangles
  详细解决方案

[U]Packing Rectangles

热度:6   发布时间:2024-01-20 20:46:42.0

很久没有做题了,详细统计呢有两个月了。浪费了两个月做了一些无关痛痒的事情。在这里对我的队友说声对不起了...接下来好好做题吧..尽量多做点多感悟一点。

分析:

这题在题目里面说得很清楚了,有6种情况,其实这六种情况只是4个矩形的不同摆法。和他的长宽怎么摆是没有关系的。其中1-5的情况是固定的,因为这几种情况比较简单,每个矩形各自的长宽对集合出的大矩形的长宽影响不大。

下面重点分析的就是第六种:


不用管题中的图怎么话,实际上6个图的意思只是矩形的位置,和长宽放置并没有关系。认真你就输了!按这样放置,其实题中图的意思也就是上面的那个图,不论长宽,只分位置。在这样放置的情况下,初始化宽度;

w=0.w+1.w;

h=max(0.h+3.h,1.h+2.h);

在图中0,3相连,1,2相连;

特殊情况呢??所谓的特殊情况就是影响初始情况的,稍加分析可以发现有以下情况:

    

根据这几种特殊情况就可以来判断了!

/*ID:seven4LANG:C++PROB:packrec */
#include<stdio.h>
#define INF 0x7FFFFFFF
using namespace std;struct REC
{int h,w;
};int max( int a,int b ){ return a>b?a:b; }
int max( int a,int b,int c ){ return a>max(b,c)?a:max(b,c); }
int max( int a,int b,int c,int d ){ return a>max(b,c,d)?a:max(b,c,d); }
int min( int a,int b ){ return a<b?a:b; }int ans;
bool flag[100];REC swap( REC R )
{int temp;temp=R.h;R.h=R.w;R.w=temp;return R;
}void record( int a,int b )
{if( ans>a*b ){ans=a*b;for( int i=0;i<100;i++ )flag[i]=false;}if( ans==a*b )flag[min(a,b)]=true;
}
void check( REC *R )
{REC temp;temp.h=temp.w=0;int index=INF;/*1.*/temp.w=temp.h=0;temp.w=max( R[0].w+R[1].w+R[2].w+R[3].w,temp.w );temp.h=max( R[0].h,R[1].h,R[2].h,R[3].h );record(temp.w,temp.h);/*2.*/temp.w=temp.h=0;temp.w=max( R[0].w+R[1].w+R[2].w,R[3].h );temp.h=R[3].w+max( R[0].h,R[1].h,R[2].h );record(temp.w,temp.h);/*3.*/temp.w=temp.h=0;temp.w=max( R[0].w+R[1].w,R[2].h )+R[3].w;temp.h=max( R[0].h+R[2].w,R[1].h+R[2].w,R[3].h );record(temp.w,temp.h);/*4,5.*/temp.w=temp.h=0;temp.w=max( R[1].w,R[2].w )+R[0].w+R[3].w;temp.h=max( R[0].h,R[3].h,R[1].h+R[2].h );record(temp.w,temp.h);/*6.*/temp.w=R[0].w+R[1].w;temp.h=max( R[0].h+R[3].h,R[1].h+R[2].h );if( R[1].h<R[0].h )temp.w=max( temp.w,R[0].w+R[2].w );if( R[1].h>R[0].h )temp.w=max( temp.w,R[1].w+R[3].w );if( R[1].h<R[3].h+R[0].h )temp.w=max( temp.w,R[2].w+R[3].w );temp.w=max( temp.w,R[2].w );temp.w=max( temp.w,R[3].w );record(temp.w,temp.h);/**/
}void rotate( REC *R,int num )
{if( num==4 ){ check(R);return ; }R[num]=swap( R[num] );rotate( R,num+1 );R[num]=swap( R[num] );rotate( R,num+1 );
}
void permutation( REC *R,int num )
{REC r;if( num==4 ){rotate( R,0 );return ;}for( int i=num;i<4;i++ ){r=R[num];R[num]=R[i];R[i]=r;permutation( R,num+1 );r=R[num];R[num]=R[i];R[i]=r;}
}int main()
{freopen( "packrec.in","r",stdin );freopen( "packrec.out","w",stdout );REC rec[4];for( int i=0;i<100;i++ ) flag[i]=0;ans=INF;for( int i=0;i<4;i++ )scanf( "%d %d",&rec[i].h,&rec[i].w );permutation( rec,0 );printf( "%d\n",ans );for( int i=0;i<100;i++ )if( flag[i] )printf( "%d %d\n",i,ans/i );scanf( "%d",&ans );return 0;
}