《凸多边形》题目分析

本题可以用动态规划解决。

如上图所示，我们把凸多边形的N个顶点按顺序编号0~N-1。

f[i][j][k]表示起点是i，最后一个点是j的k边形，面积最大是多少。

转移方程:

f[i][j][k] = max{f[i][l][k-1] + S(i, l, j) | i < l < j}

其中S(i, l, j)是三角形ilj的面积。l是我们枚举的第k-1个点。

复杂度O(N^4)。

另外这道题还有一种"随机乱搞"的做法。

1) 首先随机选择M个点，计算当前M边形的面积。

2) 然后枚举一对点A和B，其中A是选中的点，B不是选中的点。

3) 如果改成选B不选A，能使多边形面积变大，就改选并重新计算面积。

4) 重复枚举一对点的过程，直到无法通过改选使面积增大。

5) 重复若干次随机选择初始M个点的过程。取其中最大能达到的面积。