题意:
给出n个点, 求过这n个点所需的最少直线条数.
思路:
state表示点的状态,
目的是求出对于某个state, 所需的最小直线条数.
朴素地想state之间的转移情况, 记得要体现"半隐半显"的方法... 那就是枚举一个state中的任意一对点, 去掉这对点所在的直线经过的所有点, 得到state' , 答案就是ans[state] = min(ans[state], ans[state' ] + 1); 枚举所有点对即可. 因为这个state的转移是非线性的, 所以需要用dfs... 现在问题就是如何求出state到state' 的转移. 是否可以想到预处理捏?
预处理出任意两点(i, j)所在直线覆盖的点对应的stat......
阅读全文