首页 > 小仙女过生日啦

zzugzx

发表于 2020-06-16 15:42:14

题目链接题意：题解： AC代码 /* Author:zzugzx Lang:C++ Blog:blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #define f 展开全文

wxyww

发表于 2020-06-17 21:33:08

solution 如果给出的是一个凸多边形，那么问题其实就是三角剖分，用不相交的对角线将多边形划分为多个三角形，要求最大的三角形面积最小。求这个面积。用表示从第个点到第个点进行三角剖分的答案。转移就枚举一个满足，表示以这三个点为顶点的三角形的面积，这个可以直接用叉积计算。如果给出的不是凸多展开全文

blowhail

发表于 2020-06-20 17:21:39

思路：如果是凸多边形的时候，就是三角剖分问题了，状态转移方程就是dp[i][j]=min( dp[i][j] , max( triangle(a[i],a[j],a[k]) , max( dp[i][k] , dp[k][j] ) ) );其中（i<k<j） triangle()计算的是展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛