Music Festival （压状DP+单位元素的定义）

本文主要是介绍Music Festival （压状DP+单位元素的定义），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

F. Music Festival
time limit per test1 second
memory limit per test1024 megabytes
inputstandard input
outputstandard output
Music festivals should be fun, but some of them become so big that cause headache for the goers. The problem is that there are so many good attractions playing in so many stages that the simple task of choosing which shows to watch becomes too complex.

To help goers of such festivals, Fulano decided to create an app that, after evaluating the songs heard on the users' favorite streaming services, suggests which shows to watch so that there is no other combination of shows that is better according to the criteria described below:

To enjoy the experience as much as possible it is important to watch each of the selected shows from start to end;
Going to the festival and not seeing one of the stages is out of the question;
To ensure that the selection of artists is compatible with the user, the app counts how many songs from each artist the user had previously listened to on streaming services. The total number of known songs from chosen artists should be the largest possible.
Unfortunately the beta version of app received criticism, because users were able to think of better selections than those suggested. Your task in this problem is to help Fulano and write a program that, given the descriptions of the shows happening in each stage, calculates the ideal list of artists to the user.

The displacement time between the stages is ignored; therefore, as long as there is no intersection between the time ranges of any two chosen shows, it is considered that it is possible to watch both of them. In particular, if a show ends exactly when another one begins, you can watch both of them.

Input
The first line contains an integer 1≤N≤10 representing the number of stages. The following N lines describe the shows happening in each stage. The i-th of which consists of an integer Mi≥1, representing the number of shows scheduled for the i-th stage followed by Mi show descriptions. Each show description contains 3 integers ij,fj,oj (1≤ij<fj≤86400; 1≤oj≤1000), representing respectively the start and end time of the show and the number of songs of the singer performing that were previously heard by the user. The sum of the Mi shall not exceed 1000.

Output
Your program must produce a single line with an integer representing the total number of songs previously heard from the chosen artist, or −1 if there is no valid solution.

Examples
inputCopy
3
4 1 10 100 20 30 90 40 50 95 80 100 90
1 40 50 13
2 9 29 231 30 40 525
outputCopy
859
inputCopy
3
2 13 17 99 18 19 99
2 13 14 99 15 20 99
2 13 15 99 18 20 99
outputCopy
-1

思路：

•  n很小，可以联想到压状dp的使用条件。
• 如何搞：
• 准备：以 表演时间为单位 i， 看看这个 时间 i 有没有 以 它 为 表演的结束时间， 记录下这些表演的开始，那个舞台，人数
• 做： DP【i】【J（表示n的压状）】，以 时间 i ，从左到右进行更新，有上面记录的表演时，就进行 背包（刚刚好类型）更新。
• 用了这个表演，就表示用了这个所属的舞台。
• 具体看代码。

#include <bits/stdc++.h>
using namespace std;
#define ri register int
#define  M 10005

template <class G > void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}

struct dain{
    int st,val,id;
};

vector <dain> p[86400+10];   
int dp[86400+10][1030];
int n,m;

int main(){
    
    read(n);
    for(ri i=1;i<=n;i++)
    {
        read(m);
        for(ri j=1;j<=m;j++)
        {
            int a;
            dain t;
            read(t.st);read(a);read(t.val);t.id=1<<(i-1);
            p[a].push_back(t);
        }
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(ri i=1;i<=86400;i++)
    {
        for(ri j=1;j<(1<<n);j++)
        {
            dp[i][j]=dp[i-1][j];
        }
        dp[i][0]=0;
        for(ri j=0;j<p[i].size();j++)
        {
            dain t=p[i][j];
            for(ri k=0;k<(1<<n);k++)
            {
                if(dp[t.st][k]==-1) continue;           
                dp[i][k|t.id]=max(dp[i][k|t.id],dp[t.st][k]+t.val);
            }
        }
    }

    printf("%d",dp[86400][(1<<n)-1]);
    
    
}

这篇关于Music Festival （压状DP+单位元素的定义）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！