C. Boxes Packing

Codeforces

IDCF903C

Time1000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Mishka has got _n_ empty boxes. For every _i_ (1 ≤ _i_ ≤ _n_), _i_\-th box is a cube with side length _a__i_. Mishka can put a box _i_ into another box _j_ if the following conditions are met: * _i_\-th box is not put into another box; * _j_\-th box doesn't contain any other boxes; * box _i_ is smaller than box _j_ (_a__i_ < _a__j_). Mishka can put boxes into each other an arbitrary number of times. He wants to minimize the number of _visible_ boxes. A box is called _visible_ iff it is not put into some another box. Help Mishka to determine the minimum possible number of _visible_ boxes! ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 5000) — the number of boxes Mishka has got. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109), where _a__i_ is the side length of _i_\-th box. ## Output Print the minimum possible number of _visible_ boxes. [samples] ## Note In the first example it is possible to put box 1 into box 2, and 2 into 3. In the second example Mishka can put box 2 into box 3, and box 4 into box 1.

Mishka 有 #cf_span[n] 个空盒子。对于每个 #cf_span[i]（#cf_span[1 ≤ i ≤ n]），第 #cf_span[i] 个盒子是一个边长为 #cf_span[ai] 的立方体。 Mishka 可以将盒子 #cf_span[i] 放入盒子 #cf_span[j] 中，当且仅当满足以下条件： Mishka 可以任意多次将盒子嵌套放入其他盒子中。他希望最小化 _可见_ 盒子的数量。一个盒子被称为 _可见_，当且仅当它没有被放入任何其他盒子中。请帮助 Mishka 确定 _可见_ 盒子的最小可能数量！第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]）——Mishka 拥有的盒子数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 是第 #cf_span[i] 个盒子的边长。请输出 _可见_ 盒子的最小可能数量。在第一个例子中，可以将盒子 #cf_span[1] 放入盒子 #cf_span[2]，再将 #cf_span[2] 放入 #cf_span[3]。在第二个例子中，Mishka 可以将盒子 #cf_span[2] 放入盒子 #cf_span[3]，并将盒子 #cf_span[4] 放入盒子 #cf_span[1]。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]）——Mishka 拥有的盒子数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 是第 #cf_span[i] 个盒子的边长。 ## Output 请输出 _可见_ 盒子的最小可能数量。 [samples] ## Note 在第一个例子中，可以将盒子 #cf_span[1] 放入盒子 #cf_span[2]，再将 #cf_span[2] 放入 #cf_span[3]。在第二个例子中，Mishka 可以将盒子 #cf_span[2] 放入盒子 #cf_span[3]，并将盒子 #cf_span[4] 放入盒子 #cf_span[1]。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of boxes. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers representing the side lengths of the boxes. **Constraints** 1. $ 1 \leq n \leq 5000 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum number of visible boxes, where a box $ a_i $ can be placed inside box $ a_j $ if and only if $ a_i < a_j $. Boxes can be nested recursively. The goal is to minimize the number of outermost (visible) boxes. This is equivalent to finding the size of the **minimum number of decreasing subsequences** that partition the multiset $ A $, which by Dilworth’s theorem equals the size of the **longest non-decreasing subsequence** of $ A $. Thus, the minimum number of visible boxes is equal to the length of the **longest non-decreasing subsequence** of $ A $.

Samples

Input #1

3
1 2 3

Output #1

Input #2

4
4 2 4 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Boxes Packing",
    "description": {
      "content": "Mishka has got _n_ empty boxes. For every _i_ (1 ≤ _i_ ≤ _n_), _i_\\-th box is a cube with side length _a__i_. Mishka can put a box _i_ into another box _j_ if the following conditions are met: *   _",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF903C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mishka has got _n_ empty boxes. For every _i_ (1 ≤ _i_ ≤ _n_), _i_\\-th box is a cube with side length _a__i_.\n\nMishka can put a box _i_ into another box _j_ if the following conditions are met:\n\n*   _...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mishka 有 #cf_span[n] 个空盒子。对于每个 #cf_span[i]（#cf_span[1 ≤ i ≤ n]），第 #cf_span[i] 个盒子是一个边长为 #cf_span[ai] 的立方体。\n\nMishka 可以将盒子 #cf_span[i] 放入盒子 #cf_span[j] 中，当且仅当满足以下条件：\n\nMishka 可以任意多次将盒子嵌套放入其他盒子中。他希望最小化 _可...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of boxes.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing the side lengths of the boxes.\n\n**Constraints** ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments