noip15年普及组-T4-推销员

本文主要是介绍noip15年普及组-T4-推销员，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目:推销员

1. 60分解法 枚举+模拟

提出一个命题：
如果$X=1$， 走过的结点集合为 { i 1 } \{i_1\} {i1​}，
如果$X=2$， 走过的结点集合为 { i 1 , i 2 } \{i_1, i_2\} {i1​,i2​}
就是说：$X=2$的集合必然包含$X=1$的集合

证明:
v[i] ： i结点的疲劳值
dis[i]: i结点到起点的距离

当x=1时 maxNode为最大的结点, 即是V[maxNode] + dis[maxNode]*2 > v[i] + dis[j](i=j=1,2,3...)

当x=2时 假设最大的疲劳值是q = v[k1] + v[k2] + dis[k2] * 2其中dis[k2]>dis[k1] k1!=maxNode, k2!=maxNode
显然可以看出存在 v[k1] +V[maxNode] + dis[maxNode]*2 > q
所 以 假 设 不 成 立 ， k 1 或 k 2 中 必 然 有 一 个 等

这篇关于noip15年普及组-T4-推销员的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---