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;
}