UVALive - 6938 区间dp+离散化

小鱼儿 2022-05-17 12:09 151阅读 0赞

[传送门][Link 1]

思路：一条射线最小的花费就是路径上最高的那个，对于时间这个区间，我们可以将其离散化成1~600的范围，因为有三百个点，最多就600个不同的数，转移方程就是

![dp\[i\]\[j\]=min(dp\[i\]\[j\], dp\[i\]\[k\]+dp\[k\]\[j\]+cost\[id\])][dp_i_j_min_dp_i_j_ dp_i_k_dp_k_j_cost_id]， dp\[i\]\[j\]是（i，j）开区间的最小花费，id就是(i，j)时间区间中最高的外星人，k就是枚举这个外星人区间的某个时间点，将（i，j）划分为更小的区间（i，k）（k，j）。

#include<bits/stdc++.h>
    using namespace std;
    const int INF=0x3f3f3f3f;
    struct node{
        int l, r, v;
    }p[310];
    int val[620], mx, n;
    int dp[1000][1000];
    
    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", &p[i].l, &p[i].r, &p[i].v);
                val[++mx]=p[i].l; val[++mx]=p[i].r;
            }
            sort(val+1, val+1+mx);
            mx=unique(val+1, val+1+mx)-val;
    
            for(int i=1; i<=n; i++){
                p[i].l=lower_bound(val, val+mx, p[i].l)-val;
                p[i].r=lower_bound(val, val+mx, p[i].r)-val;
            
            }
    
            for(int d=2; d<=mx; d++){
                for(int i=0; i+d<=mx; i++){
                    int id=-1, j=i+d;
                    dp[i][j]=INF;
                    for(int k=1; k<=n; k++){
                        if(p[k].l>i && p[k].r<j && (id==-1 || p[id].v<p[k].v))
                            id=k;
                    }
                    
                    if(id==-1){
                        dp[i][j]=0;
                        continue;
                    }
    
                    for(int k=p[id].l; k<=p[id].r; k++){
                        dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]+p[id].v);
                    }
                }
            }
    
           
            printf("%d\n", dp[0][mx]);//注意（0，mx）=[1，mx-1]
        }
    
        return 0;
    }

[Link 1]: https://vjudge.net/problem/UVALive-6938
[dp_i_j_min_dp_i_j_ dp_i_k_dp_k_j_cost_id]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%5Bj%5D%3Dmin%28dp%5Bi%5D%5Bj%5D%2C%20dp%5Bi%5D%5Bk%5D&plus;dp%5Bk%5D%5Bj%5D&plus;cost%5Bid%5D%29