希望 线段树 01背包

　　

链接：https://ac.nowcoder.com/acm/contest/917/E
来源：牛客网

题目描述

水宝宝驾驶着毁灭号接近了勇者号舰桥。

他要使用毁灭号的等离子炮摧毁勇者号主控台。

但是操控等离子炮的程序出了点问题。等离子炮有n个操作信号，第i个操作信号的强度为b[i]。总体强度为各操作信号的强度之和。

由于有些信号太弱了了 (强度<0)，水宝宝想把它们删除。但是水宝宝自己不会删除信号，所以他找来了同船的队友帮忙。

有 m位队友，第ii 位队友只会删除编号在 L[i] 和 R[i]之间的信号，且每删除一个信号，花费 C[i]格能量。飞船一共有 k格能量，问他在请队友删除完信号后，总体强度最大是多少。

 

 

其实就是一个01背包  但是删除的代价 w 是有很多的（很多人的叠加)  只需要用线段树维护最小代价  然后再01背包一次就可以了

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
const int N=1e5+5;
int sum[N<<2],col[N<<2],w[N],c[N],k,m,n,dp[N],ans;
#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1

void up(int pos)
{
    sum[pos]=min(sum[pos<<1],sum[pos<<1|1]);
}
void down(int pos)
{
    sum[pos<<1]=min(sum[pos<<1],col[pos]);
    sum[pos<<1|1]=min(sum[pos<<1|1],col[pos]);
    col[pos<<1]=min(col[pos<<1],col[pos]);
    col[pos<<1|1]=min(col[pos<<1|1],col[pos]);
    col[pos]=inf;
}
void build(int l,int r,int pos)
{
    col[pos]=inf;
    if(l==r)
    {
        sum[pos]=inf;
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    up(pos);
}
void update(int L,int R,int v,int l,int r,int pos)
{
    if(L<=l&&r<=R)
    {
        sum[pos]=min(sum[pos],v);
        col[pos]=min(col[pos],v);
        return ;
    }
    down(pos);
    int m=(l+r)>>1;
    if(L<=m)update(L,R,v,lson);
    if(R>m)update(L,R,v,rson);
    up(pos);
}
void query(int L,int R,int l,int r,int pos)
{
    if(l==r)
    {
        w[l]=sum[pos];
        return ;
    }
    int m=(l+r)>>1;
    down(pos);
    if(L<=m)query(L,R,lson);
    if(R>m)query(L,R,rson);
    up(pos);
}
int main()
{
    RIII(n,k,m);
    rep(i,1,n)RI(c[i]),ans+=c[i];

    build(1,n,1);
    rep(i,1,m)
    {
        int u,w,v;
        RIII(u,w,v);
        update(u,w,v,1,n,1);
    }
    query(1,n,1,n,1);

    rep(i,1,n)
    repp(j,k,0)
    if(j>=w[i])
    dp[j]=max(dp[j],dp[j-w[i]]-c[i]);

    cout<<ans+dp[k];

    return 0;
}