hiho一下第191周《凸多边形》题目分析

11
0

《凸多边形》题目分析

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

week191

如上图所示,我们把凸多边形的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个点的过程。取其中最大能达到的面积。

5 answer(s)

2

1

2

ht

0

想请教一下随机乱搞的方法怎么可以保证结果一定是正确的?是因为取不到最好结果的概率很低吗?

  • 随机乱搞,我写的太渣。。WA 了 90分。。。。

  • 添加评论
  • reply
0

用"随机乱搞"的做法,假设输入:

8 4 4 0 3 3 0 4 -3 3 -4 0 -3 -3 0 -4 3 -3

首先随机选择了(4,0),(0,4),(-4,0),(0,-4)

好像结果不对……

1

都是大佬

write answer 切换为英文 切换为中文


转发分享