[DP][紫书][计算几何] UVA 1543 Telescope

题目链接 https://cn.vjudge.net/problem/UVA-1543

复习微机原理复习到吐，随便翻了个题写了写缓和一下脑子。。。。

一开始看题目给的信息总想着怎么能用到那个1/2sinα，然后就没什么头绪（后来发现给这公式只是用来计算三角形的）。后来开始想正常的dp套路，也就是以xx为结尾/开头的xx的大小，然后发现这个形状的大小不能只由一边来确定，所以加了一维表示另外一边的位置，最后整出来状态就是dp[i][j][k]表示在i到j之间选k个点能组成的最大的多边形大小，然后到这里想地推公式的时候又想挫了，总觉得会弄个复杂度n^5的出来。。。。最后发现其实只要选一个分割点分成一个三角形和一个多边形就可以了：不需要像定义状态那样两边都考虑，因为这里只是一个从大问题变小问题的过程，状态的总数是确定的，那么转移方程应该尽可能地快，所以只要能让问题规模变小就可以操作，在这些操作里选最快的那个。。

所以递推的策略就是对于i到j中选k个点组成多边形的大小，他一定可以转化为一个三角形和另一个多边形的面积和，而在这其中选择最大的数值就可以了，也就是dp[i][j][k]=max(area[i][x][j]+dp[x][j][k-1]),其中area[a][b]表示顶点为abc的三角形面积，可以n^3预处理出来，所以最后的结果就是一个n^4的算法了，对于n<=40已经足够。最后的答案取max(dp[i][j][m])即可。

代码如下：（三角形面积计算用的以圆心为参考点的有向面积和）

 

 

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn=55;
const int mod =1e9+7;
const int INF=0X3f3f3f3f;
const double pi=3.14159265358979323846;


double ps[maxn];
double area[maxn][maxn][maxn];
double dp[maxn][maxn][maxn];

double calt(double a,double b,double c)
{
    double res=0.0;
    res+=sin(2*pi*(a-b));
    res+=sin(2*pi*(b-c));
    res+=sin(2*pi*(c-a));
    return 0.5*res;
}

int main()
{
    int n,m;
    double res=0.0;
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        memset(dp,0,sizeof(dp));
        memset(area,0,sizeof(area));
        for (int i=1; i<=n; i++)
            cin>>ps[i];
        for (int i=3; i<=n; i++)
            for (int j=2; j<=i-1; j++)
                for (int k=1; k<=j-1; k++)
                    area[i][j][k]=calt(ps[i],ps[j],ps[k]);
        for (int i=3; i<=n; i++)
            for (int j=1; j<=i-2; j++)
                for (int k=3; k<=i-j+1; k++)
                    for (int x=i-1;x>=j;x--)
                        dp[i][j][k]=max(dp[i][j][k],area[i][x][j]+dp[x][j][k-1]);
        res=0.0;
        for (int i=3;i<=n;i++)
            for (int j=1;j<=i-2;j++)
            res=max(res,dp[i][j][m]);
        printf("%.6f\n",res);
    }
    return 0;
}