凸多边形三角划分（HNOI’97）

· · 个人记录

一、试题描述

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

输入文件：第一行 顶点数N

第二行 N个顶点（从1到N）的权值

输出格式：最小的和的值

各三角形组成的方式

输入示例：

5

121 122  123  245  231

输出示例：The minimum is ：

12214884

The formation of 3 triangle:

   3 4 5, 1 5 3, 1 2 3

二、试题分析

首先根据题意将凸多边形分成n-2个互不相交的三角形，我们只需要对 多边形的顶点进行一次搜索，然后不难得出状态转移方程（因为是互不相交所以其分成的三角形的顶点一定是多边形的三个相邻的顶点）f[i][j]=min{f[i][k]+f[k][j]+s[i]s[j]s[k]}

三、参考程序

#include<iostream>
#include<stdio.h>
#define MAX 100000001
using namespace std;
int f[100][100];
int s[100];

int main() {
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&s[i]);
    for(int i=1; i<=n; i++) {
        f[i][i+1]=0;
        for(int j=i+2; j<=n; j++) {
            f[i][j]=MAX;
        }
    }
    for(int i=n-2; i>=1; i--) {
        for(int j=i+2; j<=n; j++) {
            for(int k=i+1; k<j; k++) {
                int m=f[i][k]+f[k][j]+s[i]*s[j]*s[k];
                if(m<f[i][j])
                    f[i][j]=m;
            }
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}