Description
你有\(N\)个矩形，每个矩形都有一个宽\(W_i\)和高\(H_i\)。你的任务是在平面内找一个新矩形，使得\(N\)个矩形都严格在这个新矩形里面，且新矩形内的\(N\)个矩形不能重叠（可以有公共边）。
Hint
对于\(100%\)的数据，\(n <= 6, 1 <= W_i,H_i <= 1000\)。
Solution
这道题的解法比较奇葩。
对于平面内的任意一种合法放置矩形的方案，我们可以这样搞：
对于没个矩形线条从右上角开始能往左就往左，然后向下。
我们发现这些线条逆时针看起来有一定的规律，别急，我们把这个顺序存入\(S_1\)。
然后我们把矩形的左上-右下按类似方法，构建相对应的线条，把顺序存入\(S_2\)。
然后得到这两个序列，如果对于一对\(i, j\)，如果他们在\(S_1\)中的出现位置\(P\)有\(P_i < P_j\)且在\(S_2\)中的出现位置\(P\)有\(P_i < P_j\)，则我们说\(i\)在\(j\)上方；如果他们在\(S_1\)中的出现位置\(P\)有\(P_i < P_j\)且在\(S_2\)中的出现位置\(P\)有\(P_i < P_j\)，则我们说\(i\)在\(j\)左方。
有定理可以得出如果给定\(S_1, S_2\)，我们可以确定有且仅有一个摆放方案与之对应，反之亦然。
我们把具有“上”关系的两点和“左”关系的两点之间连一条有向边，构成两个拓扑图。
然后我们可以暴力求\(S_1, S_2\)的排列，然后对于每种排列顺序，我们构建两个拓扑图，在图上跑一个DP一样的东西求最长路。
那么答案就是这两条最长路的长度之积了。
对于答案取\(min\)即可。
复杂度分析：
枚举排列：\(\Theta(N!*N!)\)
建图+最长路：\(\Theta(N^3)\)
总复杂度：\(\Theta(N!*N!*N^3)\)
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include <cstdio>
int n, w[10], h[10];
int s1[10], s2[10];
bool v1[10], v2[10];
int getint() {
int r = 0; char c = getchar();
for (; c < '0' || c > '9'; c = getchar());
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r;
}
int ans = (1<<30);
int au[10], al[10];
int mu, ml;
int up[10][10], left[10][10], du[10], dl[10];
int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a < b ? a : b;}
bool uu[10], ul[10];
void UU() {
int i = 0;
while (i < n)
for (int j = 1; j <= n; ++j)
if (du[j] == 0 && !uu[j]) {
++i;
uu[j] = true;
for (int k = 1; k <= n; ++k)
if (up[j][k]) {
--du[k];
up[j][k] = 0;
au[k] = max(au[k], au[j]+h[k]);
}
}
}
void UL() {
int i = 0;
while (i < n)
for (int j = 1; j <= n; ++j)
if (dl[j] == 0 && !ul[j]) {
++i;
ul[j] = true;
for (int k = 1; k <= n; ++k)
if (left[j][k]) {
--dl[k];
left[j][k] = 0;
al[k] = max(al[k], al[j]+w[k]);
}
}
}
void solve() {
int i = 0;
for (i = 1; i <= n; ++i) {
uu[i] = ul[i] = false;
for (int j = i+1; j <= n; ++j) {
up[s1[i]][s1[j]] = 1;
du[s1[j]]++;
}
}
for (i = 1; i <= n; ++i)
for (int j = i+1; j <= n; ++j)
if (up[s2[j]][s2[i]]) {
up[s2[j]][s2[i]] = 0;
du[s2[i]]--;
left[s2[j]][s2[i]] = 1;
dl[s2[i]]++;
}
for (i = 1; i <= n; ++i) au[i] = h[i], al[i] = w[i];
mu = 0; ml = 0; UU(); UL(); for (i=1;i<=n;++i)mu=max(mu,au[i]), ml=max(ml,al[i]);
ans = min(ans, mu*ml);
return;
}
void p2(int now) {
if (now > n) {
solve();
return;
}
for (int i = 1; i <= n; ++i)
if (!v2[i]) {
s2[now] = i;
v2[i] = true;
p2(now+1);
v2[i] = false;
}
}
void p1(int now) {
if (now > n) {
p2(1);
return;
}
for (int i = 1; i <= n; ++i)
if (!v1[i]) {
s1[now] = i;
v1[i] = true;
p1(now+1);
v1[i] = false;
}
}
int main () {
freopen("rectangle.in", "r", stdin);
freopen("rectangle.out", "w", stdout);
n = getint();
for (int i = 1; i <= n; ++i) {
w[i] = getint();
h[i] = getint();
}
p1(1);
printf("%d\n", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
|