本文共 2717 字，大约阅读时间需要 9 分钟。

定义$f[i][j]$表示时间$[1,i]$内,覆盖舞台情况为$j$能得到的最大收益

我们先把时间离散化,这样最多只有$2\ast \sum M_i$个不同点,所以状态数是$2\ast \sum M_i\ast 2^N$

转移需要枚举一个节目,当然这个节目的结束时间应该小于等于$j$

这个转移复杂度为$O(\sum M_i)$,看起来无法通过

我们可以只转移以时间$i$结束的那些节目,至于之前的节目,直接继承就好了

也就是$f[i][j]=f[i-1][j]$

这样每个节目最多转移$2^N$次

总体复杂度仍然是$O(2\ast \sum M_i\ast 2^N)$

#include 
   
    #define int long long#define PI pair
    
     using namespace std;const int maxn = 2e5+5;struct Node{
       int l,r,v;};struct Node2{
       int r,v,id;};vector
     
      g[maxn];vector
      
       temp[maxn];int li[maxn],num,n,f[2005][1033];signed main(){
       cin>>n;    for(int i=0;i
       
        >k;        for(int j=1;j<=k;j++)		{
               int l,r,v;cin>>l>>r>>v;            g[i].push_back({
   l,r,v});            li[++num]=l;	li[++num]=r;        }    }    sort(li+1,li+1+num);    num=unique( li+1,li+1+num )-li-1;        for(int i=0;i
       
      
     
    
   

另一种想法,定义$f[i][j]$表示前$i$个节目,选择舞台状态是$j$的最大价值

定义$g[i][j]$表示时间为$[1,i]$内选择舞台状态为$j$的最大状态

状态数为$\sum M_i\ast 2^N$

设第$i$个节目开始时间$l$结束时间$r$价值$val$,属于第$id$个舞台

①.对于数组$f$的转移

如果不选择这个节目就直接继承上一次的状态

选择的话

$f[i][j|(1<<id)]=val+\underset{i=0}{\overset{l}{\max }}g[i][j]$

②.对于数组$g$的转移

不选择这个节目直接继承上一次的状态

选择的话

$g[r][j|(1<<id)]=f[i][j]$

区间最值套一个线段树即可(单调队列也行)(ps:代码是偷的,赛中用的上面的方法)

#include
   
    #define rep(i,a,b) for(int i=a;i<=b;i++)#define rep2(i,a,b) for(int i=a;i>=b;i--)using namespace std;const int maxn=1024;int dp[maxn][maxn],b[maxn<<1],cnt; bitset
    
     S[maxn];struct in{
       int s,t,val,id;    bool friend operator <(in w,in v){
           return w.s
     
      >1;        if(pos<=Mid) update(Now<<1,L,Mid,pos,val);        if(pos>Mid) update(Now<<1|1,Mid+1,R,pos,val);    }    int query(int Now,int L,int R,int l,int r)    {
           if(l<=L&&r>=R) return Mx[Now];        int Mid=(L+R)>>1,res=0;        if(l<=Mid) res=max(res,query(Now<<1,L,Mid,l,r));        if(r>Mid) res=max(res,query(Now<<1|1,Mid+1,R,l,r));        return res;    }}T[1024];int main(){
       int N,M,tot=0,ans=0;    scanf("%d",&N);    rep(i,0,N-1){
           scanf("%d",&M);        rep(j,1,M){
               tot++;            scanf("%d%d%d",&s[tot].s,&s[tot].t,&s[tot].val);            s[tot].id=i; b[++cnt]=s[tot].s; b[++cnt]=s[tot].t;        }    }    sort(b+1,b+cnt+1); cnt=unique(b+1,b+cnt+1)-(b+1);    sort(s+1,s+tot+1); M=(1<
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116330526 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！