FZU 2101 大三的美好时光

DP+离散化。

首先需要把时间离散化，剩下的就是简单DP。

还要判断哪些选修课与必修课时间有重合，我用了前缀和来处理。

注意：这题时间端点也不能重合。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=100000+10;
struct X
{
    int t,L,R,v;
    int tmpL,tmpR;
}p[maxn];
int n;
int lsh[2*maxn],tot;
int dp[2*maxn];

int flag[2*maxn];
int sum[2*maxn];

bool cmp(const X&a,const X&b)
{
    return a.R<b.R;
}

void read()
{
    for(int i=1;i<=n;i++)
        scanf("%d%d%d%d",&p[i].t,&p[i].tmpL,&p[i].tmpR,&p[i].v);
}

int Find(int x)
{
    int ans=tot;

    int left=0,right=tot-1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(lsh[mid]>=x) 
        {
            if(lsh[mid]==x) ans=min(ans,mid);
            right=mid-1;
        }
        else left=mid+1;
    }

    return ans+1;
}

void init()
{
    memset(flag,0,sizeof flag);
    memset(sum,0,sizeof flag);
    memset(dp,0,sizeof dp);
    tot=0;
}

void work()
{
    //离散化
    for(int i=1;i<=n;i++)
        lsh[tot++]=p[i].tmpL,lsh[tot++]=p[i].tmpR;
    sort(lsh,lsh+tot);
    for(int i=1;i<=n;i++)
        p[i].L=Find(p[i].tmpL),p[i].R=Find(p[i].tmpR);

    //把必修课所在时间标为1，并处理前缀和，便于判断选修课是否与必修课冲突
    for(int i=1;i<=n;i++)
    {
        if(p[i].t) continue;
        for(int j=p[i].L;j<=p[i].R;j++) flag[j]=1;
    }
    for(int i=1;i<=200000;i++) sum[i]=sum[i-1]+flag[i];

    sort(p+1,p+1+n,cmp);

    int pos=1;
    for(int t=1;t<=200000;t++)
    {
        dp[t]=dp[t-1];
        for(int j=pos;j<=n;j++)
        {
            if(p[j].R>t) {pos=j;break;}
            if(p[j].t==0) dp[p[j].R]=dp[p[j].L]+p[j].v;
            else if(p[j].t==1)
            {
                if(sum[p[j].R]-sum[p[j].L-1]!=0) continue;//如果与必修课时间有重合
                dp[p[j].R]=max(dp[p[j].R],dp[p[j].L]+p[j].v);
            }
        }
    }
    
    printf("%d
",dp[200000]);
}

int main()
{
    while(~scanf("%d",&n))
    {
        read();
        init();
        work();
    }
    return 0;
}