HDU 6365 Shoot Game区间dp+离散化-蒲公英云

HDU 6365 Shoot Game区间dp+离散化

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

传送门

这个题跟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
*/