tkconvex专题

贪心、dfs--Codechef TKCONVEX

题目大意: n 根木棍长度分别为ai,现在想从中选出2k 根组成两个面积大于0 的 凸k 边形,请找出一组解或判断无解 2k<=n<=1000 , 3<=k<=10 , 1<=ai<=109 solution: k 条边成为一个凸多边形的充要条件是最长边小于其他边之和 将木棍按长度排序后,按上述条件可知可行解要么是两段不相交的 连续的子序列,要么是一个连续的长为2k 的子序列 使用