这道题确实是公认的USACO Tainning Section1中最BT的一道，题目大意是有4个矩形，问所需要的最小面积的盒子把这些矩形装起来。
学习别人Blog上的方法后过的。
就是枚举出所有的情况A(4, 4) * (2 ^ 4).
1 #include < iostream > 2 #include < string > 3 #include < algorithm > 4 #include < string .h > 5 #include < vector > 6 #include < math.h > 7 #include < time.h > 8 using namespace std; 9 10 const int INF = 40005 ; 11 12 struct REC 13 { 14 int w, h; 15 REC(){} 16 REC( int ww, int hh) : w(ww), h(hh) 17 { 18 if (w > h) swap(w, h); 19 } 20 bool operator < ( const REC & t) const 21 { 22 if (w != t.w) return w < t.w; 23 else return h < t.h; 24 } 25 }rec[ 4 ]; 26 27 int use[ 4 ]; 28 int repeat[ 1005 ][ 1005 ]; 29 int fmaxArea; 30 vector < REC > ans; 31 32 int fmax( int a, int b) { return max(a, b);} 33 int fmax( int a, int b, int c) { return max(max(a, b), c);} 34 int fmax( int a, int b, int c, int d) { return max(max(a, b), max(c, d));} 35 36 void kill( int w, int h) 37 { 38 if (w * h < fmaxArea) 39 { 40 fmaxArea = w * h; 41 ans.clear(); 42 ans.push_back(REC(w, h)); 43 } 44 else if (w * h == fmaxArea) 45 { 46 ans.push_back(REC(w, h)); 47 } 48 } 49 50 void out () 51 { 52 memset(repeat, 0 , sizeof (repeat)); 53 sort(ans.begin(), ans.end()); 54 55 printf( " %d\n " , fmaxArea); 56 for ( int i = 0 ; i < ans.size(); i ++ ) 57 { 58 int w = ans[i].w; 59 int h = ans[i].h; 60 61 if (repeat[w][h] == 0 ) 62 { 63 repeat[w][h] = 1 ; 64 printf( " %d %d\n " , w, h); 65 } 66 } 67 } 68 69 void sol() 70 { 71 int ww, hh; 72 int w1 = rec[use[ 0 ]].w; 73 int w2 = rec[use[ 1 ]].w; 74 int w3 = rec[use[ 2 ]].w; 75 int w4 = rec[use[ 3 ]].w; 76 77 int h1 = rec[use[ 0 ]].h; 78 int h2 = rec[use[ 1 ]].h; 79 int h3 = rec[use[ 2 ]].h; 80 int h4 = rec[use[ 3 ]].h; 81 82 // 1 83 ww = w1 + w2 + w3 + w4; 84 hh = fmax(h1,h2,h3,h4); 85 kill(ww, hh); 86 87 // 2 88 ww = fmax(w1 + w2 + w3,w4); 89 hh = fmax(h1,h2,h3) + h4; 90 kill(ww, hh); 91 92 // 3 93 ww = fmax(w1 + w2,w3) + w4; 94 hh = fmax(h1 + h3,h2 + h3,h4); 95 kill(ww, hh); 96 97 // 4 98 ww = w1 + w2 + fmax(w3,w4); 99 hh = fmax(h1,h3 + h4,h2); 100 kill(ww, hh); 101 102 // 5 103 if (h3 >= h2 + h4) ww = fmax(w1,w3 + w2,w3 + w4); 104 else if (h3 > h4) ww = fmax(w1 + w2,w2 + w3,w3 + w4); 105 else if (h3 == h4) ww = fmax(w1 + w2,w3 + w4); 106 else if (h3 > h4 - h1) ww = fmax(w1 + w2,w1 + w4,w3 + w4); 107 else ww = fmax(w2,w1 + w4,w3 + w4); 108 109 hh = fmax(h1 + h3,h2 + h4); 110 kill(ww, hh); 111 } 112 113 void rot( int x) 114 { 115 if (x == 4 ) 116 { 117 sol(); 118 return ; 119 } 120 rot(x + 1 ); 121 swap(rec[x].h, rec[x].w); 122 rot(x + 1 ); 123 swap(rec[x].h, rec[x].w); 124 } 125 126 void dfs( int x) 127 { 128 if (x == 4 ) 129 { 130 // 说明4个都选好位置放下 131 // 然后选择方向 132 rot( 0 ); 133 return ; 134 } 135 136 for ( int i = 0 ; i < 4 ; i ++ ) 137 { 138 if (use[i] == - 1 ) 139 { 140 use[i] = x; 141 dfs(x + 1 ); 142 use[i] = - 1 ; 143 } 144 } 145 } 146 147 void go() 148 { 149 // 枚举所有的排列及翻转 150 fmaxArea = INF; 151 memset(use, - 1 , sizeof (use)); 152 dfs( 0 ); 153 out (); 154 } 155 156 int main() 157 { 158 freopen( " packrec.in " , " r " , stdin); 159 freopen( " packrec.out " , " w " , stdout); 160 161 for ( int i = 0 ; i < 4 ; i ++ ) 162 scanf( " %d%d " , & rec[i].w, & rec[i].h); 163 go(); 164 }
感谢以下链接：
http://sjtulibing.spaces.live.com/blog/cns!2F17193726A8CFC0!139.entry
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/11/1709656.html
