codeforces 822 C. Hacker, pack your bags!（思维+dp）

题目链接：http://codeforces.com/contest/822/submission/28248100

题解：多维的可以先降一下维度sort一下可以而且这种区间类型的可以拆一下区间只要加一个标记就知道这是开始区间还是结束区间具体看一下代码。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#define inf 1000000000000

using namespace std;

const int M = 2e5 + 10;

typedef long long ll;

struct TnT {

    int sta , cau , flag;

    ll val;

}a[M << 1];

bool cmp(TnT x , TnT y) {

    if(x.sta == y.sta) return x.flag > y.flag;

    return x.sta < y.sta;

}

ll dp[M];//dp[i]存储之前状态区间长度为i的最小花费

int main() {

    int n;

    ll x;

    scanf("%d%lld" , &n , &x);

    int cnt = 0;

    for(int i = 0 ; i < n ; i++) {

        int l , r;

        ll c;

        scanf("%d%d%lld" , &l , &r , &c);

        a[cnt].sta = l , a[cnt].flag = 1 , a[cnt].cau = r - l + 1 , a[cnt].val = c;

        a[++cnt].sta = r , a[cnt].flag = -1 , a[cnt].cau = r - l + 1 , a[cnt].val = c;

        cnt++;

    }

    sort(a , a + cnt , cmp);

    for(int i = 0 ; i < M ; i++) dp[i] = inf;

    ll ans = inf;

    for(int i = 0 ; i < cnt ; i++) {

        if(a[i].flag == 1) {

            ll sum = x - a[i].cau;

            if(sum >= 0) {

                if(dp[sum] < inf) ans = min(ans , a[i].val + dp[sum]);

            }

        }

        else {

            dp[a[i].cau] = min(dp[a[i].cau] , a[i].val);

        }//这里的标记决定了dp是否要更新，显然在区间结束时就可以更新dp了

    }

    if(ans < inf) printf("%lld\n" , ans);

    else printf("-1\n");

    return 0;

}

巴特西

codeforces 822 C. Hacker, pack your bags!（思维+dp）

最新文章

热门文章