[POI 2002] 滑雪者

Luogu

IDLGP8857

Time400ms

Memory128MB

DifficultyP6

动态规划 DP图论2002POI（波兰）Dilworth 定理

在某山的斜坡上有一些滑雪轨道和一个滑雪电梯，所有的轨道都是从山顶到山底。每天清晨都有一群工人检查轨道情况，他们一起乘电梯到到达山顶。接着他们沿每个人选择的轨道滑到底端，每个工人只能滑一次。工人选择的轨道可能有部分相同，每个轨道可由任一个向下滑行的工人检查。向下滑雪从高到底选择一条轨道进行。滑雪轨道由一个空地网络组成，每个空地有不同的高度。任意两个空地之间最多有一条道相连。 ## Input 第一行一个整数 $n$ 表示空地的数目。接下来 $n-1$ 行，第 $i+1$ 行的整数表示空地 $i$ 有轨道滑向它们。第一个整数 $k$ 表示空地数目，接着 $k$ 个整数，表示它们的编号（从西往东排列）。特别的，山顶编号为 $1$，山脚编号为 $n$。 ## Output 一行，表示最少需要多少个工人检查所有的滑道。 [samples] ## Note 数据范围：$2 \le n \le 5000$，给定的图是平面图。

Samples

Input #1

15
5 3 5 9 2 4
1 9
2 7 5
2 6 8
1 7
1 10
2 14 11
2 10 12
2 13 10
3 13 15 12
2 14 15
1 15
1 15
1 15

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[POI 2002] 滑雪者",
    "description": {
      "content": "在某山的斜坡上有一些滑雪轨道和一个滑雪电梯，所有的轨道都是从山顶到山底。 每天清晨都有一群工人检查轨道情况，他们一起乘电梯到到达山顶。接着他们沿每个人选择的轨道滑到底端，每个工人只能滑一次。 工人选择的轨道可能有部分相同，每个轨道可由任一个向下滑行的工人检查。向下滑雪从高到底选择一条轨道进行。 滑雪轨道由一个空地网络组成，每个空地有不同的高度。任意两个空地之间最多有一条道相连。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 400,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8857"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在某山的斜坡上有一些滑雪轨道和一个滑雪电梯，所有的轨道都是从山顶到山底。\n\n每天清晨都有一群工人检查轨道情况，他们一起乘电梯到到达山顶。接着他们沿每个人选择的轨道滑到底端，每个工人只能滑一次。\n\n工人选择的轨道可能有部分相同，每个轨道可由任一个向下滑行的工人检查。向下滑雪从高到底选择一条轨道进行。\n\n滑雪轨道由一个空地网络组成，每个空地有不同的高度。任意两个空地之间最多有一条道相连。\n\n## In...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments