王小二卖糖

测评请前往##Luogu##

题目背景

王小二的糖果店每天都在做着美味的糖果，今天他突发奇想，看着不同大小的盒子他生出了一个奇妙的想法。

题目描述

小二一共有$N$个不同大小的盒子，每个盒子有自己的长，宽，高。他想知道把这些盒子一个一个套起来，就像俄罗斯套娃一样，最多能套起来多少的盒子。

盒子不能旋转，一个盒子的宽大于另一个盒子就不能放入，不用考虑长宽互换。每个盒子中不可能同时放入$2$个独立的盒子。如$[5,5,5]$的盒子中最多只能放入$1$个$[1,1,1]$的盒子

输入输出格式

输入格式

第$1$行一个整数$N$，表示盒子的总数。

第$2$行到第$N+1$行，每行$3$个整数，表示盒子的长，宽，高。

输出格式

一个整数，表示最多能有多少个盒子套起来。

输入输出样例

输入样例#1:

5
1 9 20
5 9 10
6 10 11
12 3 9
14 19 14

输出样例#1:

3

输入样例#2:

20
32 53 44
10 14 3
48 7 43
47 45 60
30 18 53
35 16 18
40 7 43
13 5 7
36 16 19
46 18 17
54 39 19
42 24 6
24 52 42
22 27 36
41 30 25
17 1 38
48 5 13
39 33 11
45 16 56
48 6 35

输出样例#2:

4

说明

样例说明

样例#1说明:

$[5,9,10]->[6,10,11]->[14,19,14]$

样例#2说明:

$[10,14,3]->[22,27,36]->[24,52,42]->[32,53,44]$

数据说明

对于前50%的数据，盒子的大小按照顺序依次排好(长度优先于宽度优先于高度)
对于前100%的数据，盒子的总数$\lt 8000$

标程

标程#1 - CHY

#include <bits/stdc++.h>
using namespace std;

struct box
{
    int x;
    int y;
    int z;
};

bool cmp(box a, box b)  //排序判断依据为长，宽，高
{
    if (a.x > b.x)
        return true;
    else if (a.x == b.x && a.y > b.y)
        return true;
    else if (a.x == b.x && a.y == b.y && a.z > b.z)
        return true;
    else
        return false;
}

int n;
vector<box> boxes;

void getdata()
{
    cin >> n;
    box a;
    a.x = 0;
    a.y = 0;
    a.z = 0;

    vector<box> tmp(n + 1, a);
    for (int i = 0; i < n; i++)
        cin >> tmp[i].x >> tmp[i].y >> tmp[i].z;

    boxes = tmp;
    sort(boxes.begin(), boxes.end(), cmp);
    //倒序(其实我当时写反了QAQ)
}

void work()
{
    vector<int> dp(n + 1, 1);
    int ans = 0;
    //n^2/2的复杂度,期待更好做法
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = n - 1; j > i; j--)
        {
            if (boxes[i].x > boxes[j].x && boxes[i].y > boxes[j].y && boxes[i].z > boxes[j].z)
            //如果长宽高都更大就装进去
            //最长子序列
            //动态转移方程
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        //取最长
        ans = max(ans, dp[i]);
    }
    cout << ans;
}

int main()
{
    getdata();
    work();
    return 0;
}