盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 方法1
  4. 方法2
  5. 更新日志

CF 4D Mysterious Present (dp, 最长上升子序列)

题目

源地址:http://codeforces.com/problemset/problem/4/D

题意

有一个明信片,宽度为$w$,高度为$h$。以及$n$个信封,每个的宽度为$w_i$,高度为$h_i$,信封$A$的宽度和高度均大于$B$时,$B$可以装进$A$。现在要把明信片装进信封里(规则与信封嵌套一样),且要求信封嵌套的层数最多。问最多能有多少层,并输出嵌套方案。
数据范围:$1{\leq}n{\leq}5000, 1{\leq}w_i, h_i{\leq}10^6$

方法1

由于n才5000,所以可以采用记忆化搜索来做,$dp[i]$表示以$i$信封为最内层,可以有多少层。
每搜到一个信封$i$,如果之前已经搜索过了,返回$dp[i]$。
否则先操作$dp[i] = 1$(因为一个信封为$1$层)。然后对其他所有信封进行搜索,如果其中有信封$j$能作为$i$信封的外层,且$dp[j] + 1 > dp[i]$,更新$dp[i]$。
从明信片开始搜索。

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
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int N = 5010;
int n, w[N], h[N], nxt[N], dp[N];
int gao(int x) {
if (dp[x]) return dp[x];
dp[x] = 1;
for (int i = 0; i <= n; i++) if (w[i] > w[x] && h[i] > h[x]) {
if (gao(i) + 1 > dp[x]) {
nxt[x] = i;
dp[x] = dp[i] + 1;
}
}
return dp[x];
}
int main () {
cin>>n;
for (int i = 0; i <= n; i++) {
scanf("%d%d", w + i, h + i);
nxt[i] = -1;
}
gao(0);
cout<<dp[0] - 1<<endl;
for (int i = nxt[0]; i != -1; i = nxt[i]) printf("%d ", i);
return 0;
}

方法2

首先先将信封进行筛选,即去除那些装不了明信片的。然后求二维偏序集$(x,y)$的最长上升子序列即可。
求法是:先按照其中一维进行从小到大排序,第一维相同,按第二维从小到大排序,这样排序的目的是保证只有排在后面的信封才有可能装排在前面的信封。
然后按照$O(N^2)$的思想找到最长上升子序列即可。

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
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int N = 5010;
struct node {
int w, h, id;
}e[N];
bool cmp(node s, node v) {
if (s.w != v.w) return s.w < v.w;
return s.h < v.h;
}
int dp[N], pre[N];
int main () {
int n, w, h;
scanf("%d%d%d", &n, &w, &h);
int x, y, cnt = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d", &x, &y);
if (x > w && y > h) e[cnt++] = {x, y, i + 1};
}
sort(e, e + cnt, cmp);
int mx = 0, fg = -1;
for (int i = 0; i < cnt; i++) {
pre[i] = -1;
dp[i] = 1;
for (int j = 0; j < i; j++) if (e[j].w < e[i].w && e[j].h < e[i].h) {
if (dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] > mx) mx = dp[i], fg = i;
}
cout<<mx<<endl;
vector<int> v;
for (int i = fg; i != -1; i = pre[i]) v.pb(e[i].id);
reverse(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) cout<<v[i]<<" ";
if (fg != -1) cout<<endl;
}

更新日志

  • 2014-11-7 AC