DP 渡轮问题 测试数据
《轮渡问题》是一道经典的DP动态题,但网上找不到正确的测试数据,现奉献测试数据和AC代码如上。 题目描述 某国家被一条河划分为南北两部分,在南岸和北岸总共有N对城市,每一城市在对岸都有唯一的友好城市,任何两个城市都没有相同的友好城市。每一对友好城市都希望有一条航线来往,于是他们向政府提出了申请。由于河终年有雾。政府决定允许开通的航线就互不交叉(如果两条航线交叉,将有很大机会撞船)。兴建哪些航线以使在安全条件下有最多航线可以被开通。 输入 第一行两个由空格分隔的整数x,y,10〈=x〈=6000,10〈=y〈=100。x表示河的长度而y表示宽。 第二行是一个整数N(1