这是一个很蛋疼的搜索题,虽然题中只给了5种矩形组合方式,但是搜索时的长和宽并不是唯一的,所以就产生了很多种组合方式.需要注意的是第4种和第3种图形实际上能规划成一种。 而产生这些组合最好用的应该就是DFS了,而我当时不想动脑子,使用的就是纯枚举,巨大的代码量,最终好歹也能过了。
/* ID: sdj22251 PROG: packrec LANG: C++ */ #include <iostream> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cmath> #include <ctime> #define MAX 2000000000 #define M 1007 #define LOCAL using namespace std; struct wwj { int x, y; }a[4], ans[21050]; bool v[5]; wwj f1(wwj a, wwj b, wwj c, wwj d) { wwj rec; rec.x = a.x + b.x + c.x + d.x; rec.y = max(max(a.y, b.y), max(c.y, d.y)); return rec; } wwj f2(wwj a, wwj b, wwj c, wwj d) { wwj rec; rec.x = max(a.x, b.x + c.x + d.x); rec.y = a.y + max(d.y, max(b.y, c.y)); return rec; } wwj f3(wwj a, wwj b, wwj c, wwj d) { wwj rec; rec.x = max(a.x+b.x, c.x)+d.x; rec.y = max(max(a.y, b.y)+c.y, d.y); return rec; } wwj f4(wwj a, wwj b, wwj c, wwj d) { wwj rec; rec.x = a.x + max(b.x, c.x) + d.x; rec.y = max(max(a.y, b.y + c.y), d.y); return rec; } wwj f6(wwj a, wwj b, wwj c, wwj d) { wwj rec; rec.x = a.x+b.x; rec.y = max(a.y+c.y, b.y+d.y); if (a.y < b.y) rec.x = max(rec.x, c.x+b.x); if (a.y+c.y > b.y) rec.x = max(rec.x, c.x+d.x); if (b.y < a.y) rec.x = max(rec.x, a.x+d.x); rec.x = max(rec.x, c.x); rec.x = max(rec.x, d.x); return rec; } bool cmp(wwj a, wwj b) { if(a.x * a.y == b.x * b.y) return a.x < b.x; else return a.x * a.y < b.x * b.y; } int main() { #ifdef LOCAL freopen("packrec.in","r",stdin); freopen("packrec.out","w",stdout); #endif int i, j, k, q; int count = 0; for(i = 0; i < 4; i++) scanf("%d%d", &a[i].x, &a[i].y); for(i = 0; i < 4; i++) { v[i] = true; for(j = 0; j < 4; j++) { if(v[j] == true) continue; v[j] = true; for(k = 0; k < 4; k++) { if(v[k] == true) continue; v[k] = true; for(q = 0; q < 4; q++) { if(v[q] == true) continue; wwj fk1, fk2, fk3, fk4; fk1.x = a[i].y; fk1.y = a[i].x; fk2.x = a[j].y; fk2.y = a[j].x; fk3.x = a[k].y; fk3.y = a[k].x; fk4.x = a[q].y; fk4.y = a[q].x; ans[count++] = f1(a[i], a[j], a[k], a[q]); ans[count++] = f2(a[i], a[j], a[k], a[q]); ans[count++] = f3(a[i], a[j], a[k], a[q]); ans[count++] = f4(a[i], a[j], a[k], a[q]); ans[count++] = f6(a[i], a[j], a[k], a[q]); ans[count++] = f1(fk1, a[j], a[k], a[q]); ans[count++] = f2(fk1, a[j], a[k], a[q]); ans[count++] = f3(fk1, a[j], a[k], a[q]); ans[count++] = f4(fk1, a[j], a[k], a[q]); ans[count++] = f6(fk1, a[j], a[k], a[q]); ans[count++] = f1(fk1, a[j], fk3, a[q]); ans[count++] = f2(fk1, a[j], fk3, a[q]); ans[count++] = f3(fk1, a[j], fk3, a[q]); ans[count++] = f4(fk1, a[j], fk3, a[q]); ans[count++] = f6(fk1, a[j], fk3, a[q]); ans[count++] = f1(fk1, a[j], a[k], fk4); ans[count++] = f2(fk1, a[j], a[k], fk4); ans[count++] = f3(fk1, a[j], a[k], fk4); ans[count++] = f4(fk1, a[j], a[k], fk4); ans[count++] = f6(fk1, a[j], a[k], fk4); ans[count++] = f1(fk1, fk2, a[k], a[q]); ans[count++] = f2(fk1, fk2, a[k], a[q]); ans[count++] = f3(fk1, fk2, a[k], a[q]); ans[count++] = f4(fk1, fk2, a[k], a[q]); ans[count++] = f6(fk1, fk2, a[k], a[q]); ans[count++] = f1(fk1, fk2, a[k], fk4); ans[count++] = f2(fk1, fk2, a[k], fk4); ans[count++] = f3(fk1, fk2, a[k], fk4); ans[count++] = f4(fk1, fk2, a[k], fk4); ans[count++] = f6(fk1, fk2, a[k], fk4); ans[count++] = f1(fk1, fk2, fk3, a[q]); ans[count++] = f2(fk1, fk2, fk3, a[q]); ans[count++] = f3(fk1, fk2, fk3, a[q]); ans[count++] = f4(fk1, fk2, fk3, a[q]); ans[count++] = f6(fk1, fk2, fk3, a[q]); ans[count++] = f1(fk1, fk2, fk3, fk4); ans[count++] = f2(fk1, fk2, fk3, fk4); ans[count++] = f3(fk1, fk2, fk3, fk4); ans[count++] = f4(fk1, fk2, fk3, fk4); ans[count++] = f6(fk1, fk2, fk3, fk4); ans[count++] = f1(a[i], fk2, a[k], a[q]); ans[count++] = f2(a[i], fk2, a[k], a[q]); ans[count++] = f3(a[i], fk2, a[k], a[q]); ans[count++] = f4(a[i], fk2, a[k], a[q]); ans[count++] = f6(a[i], fk2, a[k], a[q]); ans[count++] = f1(a[i], fk2, a[k], fk4); ans[count++] = f2(a[i], fk2, a[k], fk4); ans[count++] = f3(a[i], fk2, a[k], fk4); ans[count++] = f4(a[i], fk2, a[k], fk4); ans[count++] = f6(a[i], fk2, a[k], fk4); ans[count++] = f1(a[i], fk2, fk3, a[q]); ans[count++] = f2(a[i], fk2, fk3, a[q]); ans[count++] = f3(a[i], fk2, fk3, a[q]); ans[count++] = f4(a[i], fk2, fk3, a[q]); ans[count++] = f6(a[i], fk2, fk3, a[q]); ans[count++] = f1(a[i], fk2, fk3, fk4); ans[count++] = f2(a[i], fk2, fk3, fk4); ans[count++] = f3(a[i], fk2, fk3, fk4); ans[count++] = f4(a[i], fk2, fk3, fk4); ans[count++] = f6(a[i], fk2, fk3, fk4); ans[count++] = f1(a[i], a[j], fk3, a[q]); ans[count++] = f2(a[i], a[j], fk3, a[q]); ans[count++] = f3(a[i], a[j], fk3, a[q]); ans[count++] = f4(a[i], a[j], fk3, a[q]); ans[count++] = f6(a[i], a[j], fk3, a[q]); ans[count++] = f1(a[i], a[j], fk3, fk4); ans[count++] = f2(a[i], a[j], fk3, fk4); ans[count++] = f3(a[i], a[j], fk3, fk4); ans[count++] = f4(a[i], a[j], fk3, fk4); ans[count++] = f6(a[i], a[j], fk3, fk4); ans[count++] = f1(a[i], a[j], a[k], fk4); ans[count++] = f2(a[i], a[j], a[k], fk4); ans[count++] = f3(a[i], a[j], a[k], fk4); ans[count++] = f4(a[i], a[j], a[k], fk4); ans[count++] = f6(a[i], a[j], a[k], fk4); } v[k] = false; } v[j] = false; } v[i] = false; } sort(ans, ans + count, cmp); printf("%d\n", ans[0].x * ans[0].y); int t = ans[0].x * ans[0].y; for(i = 0; i < count; i++) { if(ans[i].x * ans[i].y == t) { ans[i].x = min(ans[i].x, ans[i].y); ans[i].y = t / ans[i].x; } } sort(ans, ans + count, cmp); for(i = 0; i < count; i++) { if(ans[i].x * ans[i].y == ans[0].x * ans[0].y) { if(i >= 1 && ans[i].x == ans[i - 1].x) continue; printf("%d %d\n", ans[i].x, ans[i].y); } } return 0; }
附官方题解一份,代码风格让我觉得很飘渺,怎么也看的不是很懂
This program is straightforward, but a bit long due to the geometry involved.
There are 24 permutations of the 4 rectangles, and for each permutation, 16 different ways to orient them.
We generate all such orientations of permutations, and put the blocks together in each of the 6 different ways, recording the smallest rectangles we find.
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef struct Rect Rect; struct Rect { int wid; int ht; }; Rect rotate(Rect r) { Rect nr; nr.wid = r.ht; nr.ht = r.wid; return nr; } int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int tot; int bestarea; int bestht[101]; void record(Rect r) { int i; if(r.wid*r.ht < tot) *(long*)0=0; if(r.wid*r.ht < bestarea || bestarea == 0) { bestarea = r.wid*r.ht; for(i=0; i<=100; i++) bestht[i] = 0; } if(r.wid*r.ht == bestarea) bestht[min(r.wid, r.ht)] = 1; } void check(Rect *r) { Rect big; int i; /* schema 1: all lined up next to each other */ big.wid = 0; big.ht = 0; for(i=0; i<4; i++) { big.wid += r[i].wid; big.ht = max(big.ht, r[i].ht); } record(big); /* schema 2: first three lined up, fourth on bottom */ big.wid = 0; big.ht = 0; for(i=0; i<3; i++) { big.wid += r[i].wid; big.ht = max(big.ht, r[i].ht); } big.ht += r[3].ht; big.wid = max(big.wid, r[3].wid); record(big); /* schema 3: first two lined up, third under them, fourth to side */ big.wid = r[0].wid + r[1].wid; big.ht = max(r[0].ht, r[1].ht); big.ht += r[2].ht; big.wid = max(big.wid, r[2].wid); big.wid += r[3].wid; big.ht = max(big.ht, r[3].ht); record(big); /* schema 4, 5: first two rectangles lined up, next two stacked */ big.wid = r[0].wid + r[1].wid; big.ht = max(r[0].ht, r[1].ht); big.wid += max(r[2].wid, r[3].wid); big.ht = max(big.ht, r[2].ht+r[3].ht); record(big); /* * schema 6: first two pressed next to each other, next two on top, like: * 2 3 * 0 1 */ big.ht = max(r[0].ht+r[2].ht, r[1].ht+r[3].ht); big.wid = r[0].wid + r[1].wid; /* do 2 and 1 touch? */ if(r[0].ht < r[1].ht) big.wid = max(big.wid, r[2].wid+r[1].wid); /* do 2 and 3 touch? */ if(r[0].ht+r[2].ht > r[1].ht) big.wid = max(big.wid, r[2].wid+r[3].wid); /* do 0 and 3 touch? */ if(r[1].ht < r[0].ht) big.wid = max(big.wid, r[0].wid+r[3].wid); /* maybe 2 or 3 sits by itself */ big.wid = max(big.wid, r[2].wid); big.wid = max(big.wid, r[3].wid); record(big); } void checkrotate(Rect *r, int n) { if(n == 4) { check(r); return; } checkrotate(r, n+1); r[n] = rotate(r[n]); checkrotate(r, n+1); r[n] = rotate(r[n]); } void checkpermute(Rect *r, int n) { Rect t; int i; if(n == 4) checkrotate(r, 0); for(i=n; i<4; i++) { t = r[n], r[n] = r[i], r[i] = t; /* swap r[i], r[n] */ checkpermute(r, n+1); t = r[n], r[n] = r[i], r[i] = t; /* swap r[i], r[n] */ } } void main(void) { FILE *fin, *fout; Rect r[4]; int i; fin = fopen("packrec.in", "r"); fout = fopen("packrec.out", "w"); assert(fin != NULL && fout != NULL); for(i=0; i<4; i++) fscanf(fin, "%d %d", &r[i].wid, &r[i].ht); tot=(r[0].wid*r[0].ht+r[1].wid*r[1].ht+r[2].wid*r[2].ht+r[3].wid*r[3].ht); checkpermute(r, 0); fprintf(fout, "%d\n", bestarea); for(i=0; i<=100; i++) if(bestht[i]) fprintf(fout, "%d %d\n", i, bestarea/i); exit(0); }