HDU 5914 Triangle

这道题来自HDU 5914/ CCPC2016 长春现场赛 Triangle

这道题目一开始想的是打表的解法,后来发现一直WA。后来找规律发现是斐波拉契数列。

题意

有边长[1..n](n不超过20)的边,问最少去掉几个边才能使得剩下的边不能组成三角形。

证明

充分性:斐波拉契数列的任意项$l_i$,$l_j$,$l_k$均不构成三角形。
由于任意三角形三边$a$、$b$、$c$,其中($a < b < c$)均需要满足$a + b < c$。而对于斐波拉契数列中任意的边$l_{k-2} + l_{k-1} = max(l_i + l_j) = l_k, i, j < k$ ,因此不可能存在构成三角形。
必要性:在斐波拉契数列中增加任意一项,则可以构成至少一个三角形。
假设添加边长$m$在$l_i$和$l_{i+1}$之间,由于$l_i + l_{i+1} = l_{i+2}$ ,因此 $l_i + m > l_{i+2}$,因此至少构成一个三角形。
特别地,形如1, 3, 4, 7, 11…或者2, 5, 7, 12…等数列同样具有斐波拉契数列$f[i] = f[i - 1] + f[i - 2]$的性质,但是以$1, 1, …$开始的斐波拉契数列显然“利用率”最大。

打表方法

之前有试过贪心打表方法,具体地,对于每个n,枚举出所有的三角形,统计出在三角形中出现最多次数的边(如果次数相等则进行dfs搜索),不断剔除边和,并移除该边对应的三角形,直到所有三角形都被移除。但事实上这种方法是不行的。例如对n=13,算法分别移除9(出现40次)、10(40)、8(39)、11(38)、6(34)、4(25)、12(35)、3(18),但却没有移除13(30)。其构成的1, 2, 5, 7, 13并不是最优的数列。