#2965. 挖地雷DP

挖地雷DP

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一个地图上有nn200)\red{n(n≤200)}个地窖,每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任意一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。

输入格式

第一行:地窖的个数;

第二行:为依次每个地窖地雷的个数;

下面若干行: xi\red{x_i} , yi\red{y_i}表示从xi\red{x_i} 可到yi\red{y_i}xi<yi\red{x_i < y_i}

最后一行为00\red{0 0} 表示结束。

输出格式

k1k2k3...kn\red{k_1-k_2-k3...k_n} //挖地雷的顺序

挖到最多的雷。

样例

输入数据

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

输出数据

3-4-5-6
34

提示

数据范围与提示

对于 100%\red{100\%} 的数据,1n200\red{1≤n≤200}

集训线性dp练习

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-4-30 14:00
结束于
2023-4-30 16:00
持续时间
2 小时
主持人
参赛人数
16