,你可以验证下图中所有的单调上升路径的长度都不超过 3。
下面的结论指出在某些图中总会存在一个比较长的单调上升路径:
那么,G 中一定存在一个单调上升路径,它的长度大于等于 20。
证明:假设每个节点上有一个探险家。我们按权值从小到大枚举所有的边,
每次将该边连接的节点中的探险家的位置进行对调。
可以知道,每个探险家都走的是一条单调上升路径。
另外,由于共有 100个探险家,而探险家一共走了 2000 步,所以有人走了 20 步。证毕。
现在,我们的问题是:
给定一个完全图 G,它的顶点个数为一个偶数 N。
你的任务是给每条边选一个不同的权值,要使得最长的单调上升路径最短。
*以上Case#1和Case#2 分别为一个单独的样例。
该文件中有50张表格!每一张表格都满足一个很特别的性质。
你可以去观察一下这些表格。希望它们对你会有帮助。
然而表格只是作为提示,不要在代码中直接粘贴该文件或是保存过大的常数表格,否则你的代码长度将会超出OJ代码长度限制而直接不予评测。