[紫书][DP][计算几何] UVA1634 The Picnic
题目链接 https://cn.vjudge.net/problem/UVA-1634
最近有把紫书dp这一章的习题搞完的打算。。。这个题本来看vjudge上就不到20个人做想放弃的，强迫症导致开了题就得ac。
其实和之前的那个极角排序的题目感觉很像，只不过如果还是按照那个思维来的话会遇到一个问题无法解决，就是不能在保证为凸多边形的情况下满足无后效性。。。这个光从样例就可以试出来，所以就卡了半小时没有头绪。索性直接搜了。。。但是没想到这个搜题解讲的也很迷而且做的人很少，就直接去vjudge看了代码，看到dp是二维的和转移方程顿时懂了，和之前那个题一样都是枚举左下角的点，但是这个要求dp的时候考虑两维，也就是dp[i][j]表示当前左下角点对应的以i为顺时针倒数第一个点（也就是紧挨着枚举点s的点）且以就j为顺时针倒数第二个点的最大多边形面积。 继续阅读“[紫书][DP][计算几何] UVA1634 The Picnic”