1428-切呀切披萨


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:2 提交数:3 难度:3


题目描述:

有一块多边形的披萨饼,上面有很多蔬菜和肉片,我们希望沿着两个不相邻的顶点切成小三角形,并且尽可能少地切碎披萨上面的蔬菜和肉片。

可以把披萨看作一个凸多边形,任何两个顶点的连线对应的权值代表上面的蔬菜和肉片数,我们希望沿着两个不相邻的顶点切成小三角形,尽可能少地切碎披萨上面的蔬菜和肉片。那么,该问题可以归结为凸多边形的最优三角剖分问题。

假设把披萨看作一个凸多边形,标注各顶点为{v0v1…,vn}。那么怎么得到它的最优三角剖分呢?


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(0<n<1000)表示顶点的个数。
接下来为n行,n列,共n×n个整数gij((0<gij<1000)),表示顶点ij之间的权值。

输出描述:

对于每一组输入,输出最优三角剖分权值之和。
每组的输出占一行。

样例输入:

2
6
0  2  3   1   5   6
2  0  3   4   8   6
3  3  0   10  13  7
1  4  10  0   12  5
5  8  13  12  0   3
6  6  7   5   3   0
4
0 5 12 7
8 0 9 20
25 12 0 18
30 26 15 0

样例输出:

54
63

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!