题面

题目链接

大秦 为你打开 题目传送门

备用题面

有 $n$ 个箱子编号从 $1$ 到 $n$ 。

它们的长宽高分别为：$w_1,w_2,w_3,…,w_n$ ；$l_1,l_2,l_3,…,l_n$ ；$h_1,h_2,h_3,…,h_n$ 。
对于两个箱子 $i,j$ ，如果 $w_i<w_j,li<lj,hi<hj$ 同时成立。那么可以把 $i$ 套进 $j$ 中。

一个大箱子最多可以直接套一个小箱子，箱子不能旋转。

问最少可以变成多少个箱子。

思路

由于只能套一层，所以说这个就是最大独立集问题了，，，然后就又双叒叕是模板题。。。

代码

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 510;

int n;
pair<int , pair<int , int > >a[N];

int mp[N][N];
int vis[N];
int ma[N];

inline void Input() {
    read(n);
    for(int i = 1; i <= n; i++) {
        read(a[i].first, a[i].second.first, a[i].second.second);
    }
}

inline bool Check(int x, int y) {
    return  a[x].first <  a[y].first && a[x].second.first < a[y].second.first && a[x].second.second < a[y].second.second;
}

inline int Dfs(int u) {
    for(int i = 1; i <= n; i++) {
        if(!mp[u][i] || vis[i]) continue;
        vis[i] = 1;
        if(!ma[i] || Dfs(ma[i])) {
            ma[i] = u;
            return 1;
        }
    }
    return 0;
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(Check(i, j)) {
                mp[i][j] = 1;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if(Dfs(i)) ans++;
    }
    printf("%d", n - ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}