题目链接：

纠结纠结……终于出来了！IOI的题目果然是不一般，主要还是我的能力比较差，看了好多ACMer的博客看这个题的解题报告，思路是明了了，但是还是不会编码（DFS都没玩熟。。），四个矩形组成的图形只有图示的五种情况，分别讨论就行，最后一种比较复杂，需要再分情况讨论。先搜索位置，还有一点是矩形可以横放和竖放，再搜索横竖，这样就有了5*4！*2^4种情况，情况不多。

具体的思路百度别人的。。实在太多种表述方法了，我就是贴出我的C语言代码供大家参考。开始定义变量应该用数组，我没用。。。后来懒得改了，就显得比较麻烦了。。见谅……

1 #include
     
        2 #include
      
         3 #include
       
          4 int max(int x,int y) {
   return x>y?x:y;}   //定义最大值函数  5 int w1,w2,w3,w4,h1,h2,h3,h4,w,h;    //w是宽，h是高  6 int ww[6],hh[6];                    //更改各小的矩形的长宽  7 int f[6],flag[6],p[6],x[110],y[110];   //f记录排列，flag标记数组，p记录横放竖放，x记录最小面积下的宽，y记录最小面积下的高  8 int i,s,t,min,count,ok;  //count记满足最小面积的宽高数目  9 int cmp1(void const *_a,void const *_b)  10 { 11     int *a=(int *)_a; 12     int *b=(int *)_b; 13     return *a>*b; 14 } 15 int cmp2(void const *_a,void const *_b) 16 { 17     int *a=(int *)_a; 18     int *b=(int *)_b; 19     return *a<*b; 20 } 21 void com(int s)   //记录面积最小的长宽 22 { 23     if(w>h)   //宽小高大 24     { 25         t=w; 26         w=h; 27         h=t; 28     } 29     if(min>s)   //出现面积更小的数组要清零 30     { 31         min=s; 32         count=0; 33         x[count]=w; 34         y[count]=h; 35         count++; 36     } 37     else if(min==s) 38     { 39         ok=0; 40         for(i=0;i
        
         =h2+h4) 74     { 75         w=max(w1,max(w2+w3,w3+w4)); 76         h=h3+h1; 77     } 78     else if((h3>h4)&&(h3
         
          h3)&&(h4
          
           =h1+h3) 89 { 90 w=max(w2,max(w1+w4,w3+w4)); 91 h=h2+h4; 92 } 93 else if(h3==h4) 94 { 95 h=max(h1+h3,h2+h4); 96 w=max(w1+w2,w3+w4); 97 } 98 s=w*h; 99 com(s);100 }101 void DFS_hs(int x) //dfs横竖102 {103 if(x>4)104 {105 w1=(p[1]==0)?ww[f[1]]:hh[f[1]]; h1=(p[1]==1)?ww[f[1]]:hh[f[1]];106 w2=(p[2]==0)?ww[f[2]]:hh[f[2]]; h2=(p[2]==1)?ww[f[2]]:hh[f[2]];107 w3=(p[3]==0)?ww[f[3]]:hh[f[3]]; h3=(p[3]==1)?ww[f[3]]:hh[f[3]];108 w4=(p[4]==0)?ww[f[4]]:hh[f[4]]; h4=(p[4]==1)?ww[f[4]]:hh[f[4]];109 //printf("%d %d %d %d\n",p[1],p[2],p[3],p[4]);110 cals();111 }112 else113 {114 p[x]=0;115 DFS_hs(x+1);116 p[x]=1;117 DFS_hs(x+1);118 }119 }120 void dfs(int a) //dfs排列121 {122 int i,j;123 for(i=1;i<=4;i++)124 {125 if(!flag[i])126 {127 flag[i]=1;128 f[a]=i;129 if(a<4)130 dfs(a+1);131 else132 {133 DFS_hs(1);134 // printf("x=%d y=%d min=%d\n",x[count-1],y[count-1],min);135 //system("pause");136 }137 flag[i]=0;138 }139 }140 }141 void print() //按序打印输出142 {143 printf("%d\n",min);144 qsort(x,count,sizeof(int),cmp1);145 qsort(y,count,sizeof(int),cmp2);146 for(i=0;i
          
         
        
       
      
     

用的内存比较多，但是时间效率还不错，虽然没有优化。。。

Executing...

   Test 1: TEST OK [0.000 secs, 2052 KB]

   Test 2: TEST OK [0.000 secs, 2052 KB]

   Test 3: TEST OK [0.000 secs, 2052 KB]

   Test 4: TEST OK [0.000 secs, 2052 KB]

   Test 5: TEST OK [0.000 secs, 2052 KB]

   Test 6: TEST OK [0.000 secs, 2052 KB]

   Test 7: TEST OK [0.000 secs, 2052 KB]

   Test 8: TEST OK [0.000 secs, 2052 KB]

   Test 9: TEST OK [0.000 secs, 2052 KB]

   Test 10: TEST OK [0.000 secs, 2052 KB]

   Test 11: TEST OK [0.000 secs, 2052 KB]

   Test 12: TEST OK [0.000 secs, 2052 KB]

   Test 13: TEST OK [0.000 secs, 2052 KB]

   Test 14: TEST OK [0.000 secs, 2052 KB]

   Test 15: TEST OK [0.000 secs, 2052 KB]

   Test 16: TEST OK [0.000 secs, 2052 KB]

   Test 17: TEST OK [0.000 secs, 2052 KB]

   Test 18: TEST OK [0.000 secs, 2052 KB]

   Test 19: TEST OK [0.000 secs, 2052 KB]

   Test 20: TEST OK [0.000 secs, 2052 KB]

   Test 21: TEST OK [0.000 secs, 2052 KB]

 

All tests OK.