链接
传送门
题意
有一个卡片要装到信封里，给出卡片和所有信封的长和宽，求最多可以在卡片套几层。
思路
DAG上的DP，注意信封不能旋转。
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 5010;
int d[maxn], ans[maxn], n;
int w[maxn], h[maxn];
int dp(int x) {
if (d[x] != -1) return d[x];
int& k = d[x];
k = 0;
for (int i = 0; i <= n; ++i) {
if (w[x] < w[i] && h[x] < h[i]) {
int tmp = dp(i) + 1;
if (d[x] < tmp) {
d[x] = tmp;
ans[x] = i;
}
}
}
return k;
}
int main() {
scanf("%d", &n);
for (int i = 0; i <= n; ++i) {
scanf("%d%d", &w[i], &h[i]);
}
memset(d, -1, sizeof d);
dp(0);
printf("%d\n", d[0]);
if (d[0] == 0) {
return 0;
}
int cur = 0;
while (ans[cur] != 0) {
printf("%d ", ans[cur]);
cur = ans[cur];
}
return 0;
}
|