问题:
http://ace.delos.com/usacoprob2?a=CTINrbaHwEW&S=packrec思路:
这题不会，考虑的时候以为任意两个矩阵至少存在相同的边才可以合并...结果完全错误
参考:
http://starforever.blog.hexun.com/2097115_d.htmlhttp://greenmoon55.com/usaco-packing-rectangles/另外，这题学会了在C里面使用bool类型，原来不知道呢(*^__^*) 嘻嘻……
stdbool.h头文件
代码:
1 /*
2 ID: simplyz2
3 LANG: C
4 TASK: packrec
5 */
6 #include<stdio.h>
7 #include<stdbool.h>
8 #include<stdlib.h>
9 #include<string.h>
10 #define MAX_NUM 5
11 #define INF 0x7FFFFFFF
12 #define Max(a, b) ((a)>(b) ? (a) : (b))
13 struct Rec {
14 int h, w;
15 } rectangle[MAX_NUM], rect[MAX_NUM], ans[MAX_NUM];
16 bool used[MAX_NUM];
17 int w, h, total, area;
18
19 void
20 exchange(struct Rec *r)
21 {
22 int temp = r->h;
23 r->h = r->w;
24 r->w = temp;
25 }
26
27 void
28 judge()
29 {
30 int i, j, temp;
31 if(w > h) {
32 temp = w;
33 w = h;
34 h = temp;
35 }
36 if(w*h <= area) {
37 if(w*h == area) {
38 for(i=1; i<total; i++)
39 if(ans[i].w == w)
40 return;
41 for(i=1; i<total; i++)
42 if(ans[i].w > w) {
43 for(j=total; j>i; j--)
44 ans[j] = ans[j-1];
45 ans[i].w = w;
46 ans[i].h = h;
47 ++total;
48 return;
49 }
50 ans[total].w = w;
51 ans[total++].h = h;
52 } else {
53 area = w*h;
54 total = 1;
55 ans[total].w = w;
56 ans[total].h = h;
57 }
58 }
59 }
60
61 void
62 work()
63 {
64 //Case 1
65 w=rect[1].w+rect[2].w+rect[3].w+rect[4].w;
66 h=Max(rect[1].h,rect[2].h);
67 h=Max(h,rect[3].h);
68 h=Max(h,rect[4].h);
69 judge();
70
71 //Case 2
72 w=Max(rect[1].w+rect[2].w+rect[3].w,rect[4].w);
73 h=Max(rect[1].h,rect[2].h);
74 h=Max(h,rect[3].h);
75 h+=rect[4].h;
76 judge();
77
78 //Case 3
79 w=Max(rect[1].w+rect[2].w,rect[3].w)+rect[4].w;
80 h=Max(Max(rect[1].h,rect[2].h)+rect[3].h,rect[4].h);
81 judge();
82
83 //Case 4
84 w=rect[1].w+Max(rect[2].w,rect[3].w)+rect[4].w;
85 h=Max(rect[1].h,rect[4].h);
86 h=Max(h,rect[2].h+rect[3].h);
87 judge();
88
89 //Case 6
90 if (rect[3].h>=rect[2].h+rect[4].h)
91 {
92 w=Max(rect[3].w+rect[2].w,rect[3].w+rect[4].w);
93 w=Max(w,rect[1].w);
94 h=rect[1].h+rect[3].h;
95 judge();
96 return;
97 }
98 if (rect[3].h>rect[4].h)
99 {
100 w=Max(rect[1].w+rect[2].w,rect[2].w+rect[3].w);
101 w=Max(w,rect[4].w+rect[3].w);
102 h=Max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
103 judge();
104 return;
105 }
106 if (rect[3].h==rect[4].h)
107 {
108 w=Max(rect[1].w+rect[2].w,rect[3].w+rect[4].w);
109 h=Max(rect[1].h,rect[2].h)+rect[3].h;
110 judge();
111 return;
112 }
113 if (rect[3].h<rect[4].h && rect[4].h<rect[3].h+rect[1].h)
114 {
115 w=Max(rect[1].w+rect[2].w,rect[1].w+rect[4].w);
116 w=Max(w,rect[3].w+rect[4].w);
117 h=Max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
118 judge();
119 return;
120 }
121 w=Max(rect[2].w,rect[1].w+rect[4].w);
122 w=Max(w,rect[3].w+rect[4].w);
123 h=rect[4].h+rect[2].h;
124 judge();
125 }
126
127 void
128 rotate(int depth)
129 {
130 if(depth == MAX_NUM) {
131 work();
132 return;
133 }
134 rotate(depth+1);
135 exchange(rect+depth);
136 rotate(depth+1);
137 }
138
139 void
140 dfs(int depth)
141 {
142 int i;
143 if(depth == MAX_NUM) {
144 rotate(1);
145 return;
146 }
147 for(i=1; i<MAX_NUM; i++) {
148 if(!used[i]) {
149 used[i] = true;
150 rect[depth] = rectangle[i];
151 dfs(depth+1);
152 used[i] = false;
153 }
154 }
155 }
156
157 int
158 main(int argc, char **argv)
159 {
160 int i;
161 freopen("packrec.in", "r", stdin);
162 freopen("packrec.out", "w", stdout);
163 for(i=1; i<MAX_NUM; i++)
164 scanf("%d %d", &rectangle[i].w, &rectangle[i].h);
165 total = 1;
166 area = INF;
167 memset(used, 0, sizeof(used));
168 dfs(1);
169 printf("%d\n", area);
170 for(i=1; i<total; i++)
171 printf("%d %d\n", ans[i].w, ans[i].h);
172 return 0;
173 }