HDU 6365 Shoot Game区间dp+离散化

叁歲伎倆 2022-05-17 12:11 195阅读 0赞

[传送门][Link 1]

这个题跟UVALive - 6938，的思路是一样的，感觉没做过那个题，这个题真的不好想。具体思路可以看

[\-》这个题][-]

然后这个题就是将区间转化成了极角的区间，然后对极角区间离散化，同一个角度里的物体，取花费最高的那一个。还有就是这个题x，y， w值都比原来的题大，所以dp用long long ，极角排序的时候也要转化成long long

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    struct inter{
        int l, r, h;
        ll v;
    }ob[310];
    
    struct node{
        int x, y;
    }val[620];
    int mx, n, cnt;
    ll dp[1000][1000];
    bool cmp(node a, node b){
        return 1ll*a.x*b.y-1ll*a.y*b.x<=0;
    }
    
    inline void addval(int i){
        int tmp=__gcd(abs(ob[i].l), abs(ob[i].h));
        val[++mx]=(node){ob[i].l/tmp, ob[i].h/tmp};
        tmp=__gcd(abs(ob[i].r), abs(ob[i].h));
        val[++mx]=(node){ob[i].r/tmp, ob[i].h/tmp};
    }
    
    void lisan(){
        sort(val+1, val+1+mx, cmp);
        int x=1000000001, y=0;
        cnt=0;
        for(int i=1; i<=mx; i++){
            if(val[i].x!=x||val[i].y!=y){
                x=val[i].x, y=val[i].y;
                val[++cnt].x=x; val[cnt].y=y;
            }
        }
    
        for(int i=1; i<=n; i++){
            int x1, x2, y1, y2;
            int tmp=__gcd(abs(ob[i].l), abs(ob[i].h));
            x1=ob[i].l/tmp, y1=ob[i].h/tmp;
            tmp=__gcd(abs(ob[i].r), abs(ob[i].h));
            x2=ob[i].r/tmp; y2=ob[i].h/tmp;
            for(int j=1; j<=cnt; j++){
                if(val[j].x==x1&&val[j].y==y1)
                    ob[i].l=j;
                if(val[j].x==x2 && val[j].y==y2)
                    ob[i].r=j;
            }
        }
    }
    
    int main(){
        int T;
        scanf("%d", &T);
        while(T--){
            mx=0;
            scanf("%d", &n);
            for(int i=1; i<=n; i++){
                scanf("%d%d%d%lld", &ob[i].h, &ob[i].l, &ob[i].r, &ob[i].v);
                addval(i);
            }
            lisan();
    
            for(int d=2; d<=cnt+1; d++){
                for(int i=0; i+d<=cnt+1; i++){
                    int j=i+d, id=-1;
                    dp[i][j]=INF;
                    for(int k=1; k<=n; k++){
                        if(ob[k].l>i&&ob[k].r<j&&(id==-1||ob[id].v<ob[k].v))
                            id=k;
                    }
                    if(id==-1){
                        dp[i][j]=0;
                        continue;
                    }
                    for(int k=ob[id].l; k<=ob[id].r; k++){
                        dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]+ob[id].v);
                    }
                }
            }
            printf("%lld\n", dp[0][cnt+1]);
        }
        return 0;
    }
    /*
    1
    3
    1 1 2 2
    2 -1 1 4
    3 -2 -1 3
    3
    1 -1 -1 10
    2 -2 -2 1
    1 1 1 100
    
    */

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6365
[-]: https://blog.csdn.net/du_lun/article/details/81583822