题目链接

题解

一个我想不到的性质:每个点至多会被覆盖两次。
因为如果一个点被覆盖三次,那么肯定有一条线段的效果是可以被另外两条完全表达出来的,所以可以删去这个线段。
我们先将线段按照右端点排个序,有了这个性质,又因为它是个最优化问题,启发我们设 $f_{i,j}$ 表示考虑到了前 $i$ 个线段,最后一段被覆盖了一次的线段是 $[j,r_i]$ 的最小代价。答案就是所有 $r_i = n$ 的 $f_{i,*}$ 的最小值。
考虑转移:我们枚举上一条线段 $j$,如果 $r_j < l_i$ 那么显然不能转移(会留下空),但是我们也要注意如果 $j$ 是被 $i$ 完全包含的也不能从这里转移,因为会少算其它线段的影响(没错我一开始就挂了)。分类讨论:
1. $r_j + 1 = l_i$,所以 $[l_i,r_i]$ 没有被覆盖过,$f_{j,[1,r_i]}$ 和 $w_i$ 取 max。
2. $r_j \in [l_i,r_i)$,所以有一段被覆盖过,$f_{j,[1,l_i]}$ 和 $w_i+w_j$ 取 max。
直接转移是 $O(n^2m)$ 的,使用前缀和优化可以做到 $O(n^2+nm)$。

代码

/*
 * Author: RainAir
 * Time: 2019-10-27 15:07:46
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3000+5;

struct Node{
    int l,r,w;
    bool operator < (const Node &t) const {
        return r == t.r ? l < t.l : r < t.r;
    }
}a[MAXN];
int n,m;
int f[MAXN][MAXN],g[MAXN][MAXN],h[MAXN][MAXN];
// f:f g:min h:pos

inline void Solve(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
    std::sort(a+1,a+n+1);
    FOR(i,0,n+1) FOR(j,0,m+1) f[i][j] = g[i][j] = 1e9,h[i][j] = -1;
  //  FOR(i,1,n){
 //       printf("%d %d %d\n",a[i].l,a[i].r,a[i].w);
 //   }
    FOR(i,1,n){
        if(a[i].l == 1) f[i][1] = a[i].w;
        FOR(j,1,i-1){
            if(a[j].l >= a[i].l) continue;
            if(a[j].r == a[i].r) continue;
            if(a[j].r >= a[i].l){
    //            if(a[j].r+1 == 16 && i == n) DEBUG(j);
                f[i][a[j].r+1] = std::min(f[i][a[j].r+1],std::max(a[i].w+a[j].w,g[j][a[i].l]));
            }
            else{
                if(a[j].r+1 == a[i].l){
                    if(h[j][a[j].r] != -1){
                        f[i][h[j][a[j].r]] = std::min(f[i][h[j][a[j].r]],std::max(a[i].w,g[j][a[j].r]));
                    }
                }
            }
        }
//        if(i == 12) {FOR(j,1,m) printf("%d ",f[i][j]);puts("");}
        FOR(j,1,a[i].r){
            g[i][j] = g[i][j-1],h[i][j] = h[i][j-1];
            if(f[i][j] < g[i][j]){
                g[i][j] = f[i][j];
                h[i][j] = j;
            }
        }
    }
    int ans = 1e9;
    //FOR(i,1,n) if(a[i].r == m) DEBUG(g[i][m]);
    FOR(i,1,n) if(a[i].r == m) ans = std::min(ans,g[i][m]);
    printf("%d\n",ans == 1e9 ? -1 : ans);
//    exit(0);
}

int main(){
    freopen("intervals.in","r",stdin);
    freopen("intervals.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/934/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏