凸多边形划分题解

· · 个人记录

这一道题是一道经典的区间dp题。

首先是题面：

题目描述 ###

给定一具有N个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？

输入输出格式

输入格式：

第一行 顶点数N（N<50）。 第二行 N个顶点（从1到N）的权值，权值为小于32768的整数。

输出格式：

第一行为各三角形顶点的权的乘积之和最小值。

输入输出样例

输入样例：

5 121 122 123 245 231

输出样例：

12214884

这一道题如果直接用暴搜的话，效率太低了，复杂度是O(n!), 只能得解决n <= 11的数据。

因此这道题需要用到dp的思想。

这里dp的意思是这样的。每一个多边形都一定可以通过顶点相连的方法分割为许多三角形。因此每一个三角形就可以把一个大的多边形一个三角形和两边的两个凸多边形。因此就可以进行区间dp了。

这样的时间复杂度就是枚举顶点和分割点，因此复杂度是O(n^3) DP部分代码：

for(int l = n - 2; l; l--)
    for(int r = l + 2; r <= n; r++)
        for (int k = l + 1; k < r; k++)
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);

状态转移方程：

dp[l][r] = min(dp[l][k] + dp[k][r] + a[l] * a[k] * a[r])