本文共 2090 字，大约阅读时间需要 6 分钟。
题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4077
题目大意： 给出一个多边形， 输出三角剖分最大三角形最小化的最大三角形面积
解题思路： 最大值最小化啊......猛然想到了二分， 但是这个是DP专题啊......d(i, j)表示多边形i ~ j的最优解， DP转移方程就是dp(i, j) = min(dp(i, j), max(dp(i, k), dp(k, j), get_Area(i, j, k)))
下标是可以循环的， 我们先枚举长度， 再枚举左端点，然后再枚举中的点。有个trick, 如果是三个点组成的三角形有内点的话， 这三个点组成的三角形面积不算。 画图就知道了。
代码：
#include #include #include #include #include #include #include #include #include #include #include using namespace std;struct Node { double x, y;};Node a[55];double d[55][55]; // d[i][j] zconst int INF = 0x3fffffff;int m;const double eps = 1e-9;double area( int i, int j, int k ) { return 0.5 * abs(a[i].x*(a[j].y-a[k].y)+a[j].x*(a[k].y-a[i].y)+a[k].x*(a[i].y-a[j].y));}int judge( int p, int q, int r ) { // p, q, r组成的三角形无内点 double cur = area(p, q, r); for( int i = 0; i < m; i++ ) { if( i == p || i == q || i == r ) continue; double temp = area(p, q, i) + area(q, r, i) + area(p, r, i); if( fabs(temp-cur) < eps ) return 0; } return 1;}int main() { int T; scanf( "%d", &T ); while( T-- ) { memset(a, 0, sizeof(a)); scanf( "%d", &m ); for( int i = 0; i < m; i++ ) { scanf( "%lf%lf", &a[i].x, &a[i].y ); } for( int i = 0; i < m; i++ ) { for( int j = 0; j < m; j++ ) { if( i == 0 || i == 1 ) d[j][(j+i)%m] = 0.; else if( i == 2 ) d[j][(j+i)%m] = area(j, (j+1)%m, (j+2)%m); else d[j][(j+i)%m] = INF; } } for( int k = 3; k < m; k++ ) { for( int i = 0; i < m; i++ ) { int t = (i+k)%m; // 右端点// d[i][t] = INF; for( int j = (i+1)%m; j != t; j = (j+1)%m ) { if( judge(j, t, i) ) { d[i][t] = min(d[i][t], max({d[i][j], d[j][t], area(i, j, t)})); } } } }// for( int i = 0; i < m; i++ ) {// for( int j = 0; j < m; j++ ) {// printf( "%.1lf ", d[i][j] );// }// cout << endl;// } printf( "%.1lf\n", d[0][m-1] ); } return 0;}
思考： 状态又想错了， 以后要是有点的话， 要考虑区间， 或者前i个点这种情况， 自己的心思不够缜密， 有好多漏解的情况， 还有Trick也想不到， 有时候真的感觉自己白学了一年......但是还是得接着学啊！
转载于:https://www.cnblogs.com/FriskyPuppy/p/7278720.html
