hdu 6365 Shoot Game （区间dp+极角离散）

http://acm.hdu.edu.cn/showproblem.php?pid=6365

题意:在二维平面的第一象限和第四象限上有 n 条线段表示 n 堵墙，每堵墙有一个坚固度 wi ，表示只有不小于 wi 的能量才能摧毁并贯穿它。你只能从原点向任意方向发射任意能量，问至少需要发射多少能量才能把所有的墙都摧毁。

思路：

将所有端点按极角序进行离散化，端点下标为1到2n。

设立状态

，表示消灭端点在

区间的所有线段，所需要花费的最小能量。

基于第二点，每次将区间内所包含的防御力最大的障碍物找出来，进行区间DP的转移：

最终的

即是答案。

的

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=620;
struct node
{
    int x,y;
    int id;
    node(){}
    node(int a,int b,int i):x(a),y(b),id(i){}
    bool operator < (const node &rhs) const {return 1ll*x*rhs.y-1ll*y*rhs.x<0;}
    bool operator == (const node &rhs) const {return 1ll*x*rhs.y-1ll*y*rhs.x==0;}
}p[maxn];
int l[maxn],r[maxn],w[maxn],h[maxn];
int cnt;
ll dp[maxn][maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&h[i],&l[i],&r[i],&w[i]);
            p[++cnt]=node(l[i],h[i],i);
            p[++cnt]=node(r[i],h[i],i);
        }
        sort(p+1,p+1+cnt);
        cnt=unique(p+1,p+1+cnt)-(p+1);
        for(int i=1;i<=n;i++)
        {
            l[i]=lower_bound(p+1,p+1+cnt,node(l[i],h[i],i))-p;
            r[i]=lower_bound(p+1,p+1+cnt,node(r[i],h[i],i))-p;
        }
        for(int len=1;len<=cnt;len++)
        {
            for(int i=1;i+len-1<=cnt;i++)
            {
                int j=i+len-1;
                dp[i][j]=(1LL<<60);
                int L=0,R=0,ma=-1;
                for(int k=1;k<=n;k++)
                {
                    if(i<=l[k]&&r[k]<=j&&w[k]>ma)
                    {
                        ma=w[k];
                        L=l[k];
                        R=r[k];
                    }
                }
                if(ma==-1)
                {
                    dp[i][j]=0;
                    continue;
                }
                for(int k=L;k<=R;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+ma);
                }
            }
        }
        printf("%lld\n",dp[1][cnt]);
    }
    return 0;
}