文件名称：DP-渡轮问题-测试数据
文件大小：108KB
文件格式：ZIP
更新时间：2022-05-26 15:10:47
NOIP 动态规划
《轮渡问题》是一道经典的DP动态题，但网上找不到正确的测试数据，现奉献测试数据和AC代码如上。 题目描述 某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市，每一城市在对岸都有唯一的友好城市，任何两个城市都没有相同的友好城市。每一对友好城市都希望有一条航线来往，于是他们向*提出了申请。由于河终年有雾。*决定允许开通的航线就互不交叉（如果两条航线交叉，将有很大机会撞船）。兴建哪些航线以使在安全条件下有最多航线可以被开通。 输入 第一行两个由空格分隔的整数x，y，10〈=x〈=6000，10〈=y〈=100。x表示河的长度而y表示宽。 第二行是一个整数N(1<=N<=5000)，表示分布在河两岸的城市对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D〈=x〉，描述每一对友好城市与河起点的距离，C表示北岸城市的距离而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。 输出 在安全条件下能够开通的最大航线数目。 样例输入 30 4 5 4 5 2 4 5 2 1 3 3 1 样例输出 3
【文件预览】：
test5.out
test4.out
test7.in
test6.in
test3.in
test0.in
test2.out
test3.out
test4.in
test1.in
test1.out
test8.out
test6.out
test0.out
1320.cpp
test8.in
test2.in
test9.in
test9.out
test7.out
test5.in