【题解】Music Festival(树状数组优化dp)

Gym - 101908F

题意：有\(n\)种节目，每种节目有起始时间和结束时间和权值。同一时刻只能看一个节目(边界不算)，在所有种类都看过至少一遍的情况下最大收益

设\(dp(s,i)\)表示已经看过\(s\)集合中的节目，且看过的节目的结束时间是\(i\)的最大收益。

转移：

\[dp(s,e[t].r)=\max(dp(s,k),dp(s-e[t].id,k))+e[t].val,k\le e[t].l
\]

由于\(O(m^3)\)不能过1000，但可以看到转移是一段前缀，所以直接树状数组优化就好。

注意转移的顺序，可以发现\(r\)可以作为转移状态。可能会有r相同的情况，但不影响答案。

复杂度\(O(m^2\log m)\)

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(!isdigit(c))f|=c==45,c=getchar();

      while(isdigit(c)) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=86405;

const int inf=0x3f3f3f3f;

int dp[1<<10|1][maxn];

struct E{

      int l,r,id,val;

      inline bool operator <(const E&a)const{return r<a.r;}

}e[1001];

int n,cnt,len;

inline int que(const int&pos,const int*a){

      int ret=-inf;

      for(int t=pos;t>0;t-=t&-t) ret=max(ret,a[t]);

      return ret;

}

inline void upd(const int&pos,const int&tag,int*a){

      for(int t=pos;t<=len;t+=t&-t) a[t]=max(a[t],tag);

}

int main(){

#ifndef ONLINE_JUDGE

      freopen("in.in","r",stdin);

      //freopen("out.out","w",stdout);

#endif

      n=qr();

      memset(dp,0xcc,sizeof dp);

      for(int t=1;t<=n;++t){

	    int m=qr();

	    for(int i=1,t1,t2,t3;i<=m;++i) t1=qr(),t2=qr(),t3=qr(),e[++cnt]={t1,t2,t,t3};

      }

      sort(e+1,e+cnt+1);

      len=e[cnt].r+1;

      memset(dp[0],0,sizeof dp[0]);

      for(int t=1;t<=cnt;++t){

	    for(int s=0;s<1<<n;++s){

		  if(s&(1<<e[t].id>>1)){

			int g=s^(1<<e[t].id>>1);

			int f=max(que(e[t].l,dp[s]),que(e[t].l,dp[g]))+e[t].val;

			upd(e[t].r,f,dp[s]);

		  }

	    }

      }

      int g=que(len,dp[(1<<n)-1]);

      cout<<max(g,-1)<<endl;

      return 0;

}

巴特西

【题解】Music Festival(树状数组优化dp)

【题解】Music Festival(树状数组优化dp)

最新文章

热门文章