首页 > itarticle > luoguoj p1803 messy yyy

luoguoj p1803 messy yyy

admin 11月 12, 2020 0

Problem Description

Problem URL:Messt-yyy

NOIp contest is comming,yyy is busy participating in contests.Because yyy is not a bully IOer,he can only take part in one contest at the same moment.
Now give you his contest schedule and yyy wants you to figure out how many contests which he listed on the schedule he can participate in at most.
Sample Input:
3
0 2
2 4
1 3

Sample Output:
2

Explanation:He can take part in the first contest and the second.

Problem Analysis

Though this problem can be solved by using greedy strategy,I strongly recommend the DP Solution.
Provide S[i] stands for the ending moment of contest who ends at the ith moment. Obviously,the bigger P[i] is better.Then we can get the transitional function:
$$F[i]=max(F[i-1],F[P[i]]) (if P[i]!=FLAG)$$
$$F[i]=F[i-1] (if P[i]==FLAG)$$

Explanation:the first function shows that if there is a contest starts at P[i] and ends at i,we compare wether we choose the previous contest can get a grater answer.
The Second function shows that if there isn’t any contest starts at P[i],we pass a previous value to current one.

AC CODE

Time Consumption:Unknown(Less than 1000ms)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000001;

int st[MAXN];
int maxIn=-1000;
int dp[MAXN];
int ans=-10000;
inline int max1(int a,int b){
    return a>b?a:b;
}

inline void init(){
    memset(st,-1,sizeof(st));
    memset(dp,0,sizeof(dp));
}

inline void in(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        st[e]=max1(st[e],s);
        maxIn=max1(e,maxIn);
    }
}

inline void solve(){
    for(int i=0;i<=maxIn;++i){
        if(st[i]!=-1) dp[i]=max1(dp[st[i]]+1,dp[i-1]);
        else dp[i]=dp[i-1];
        ans=max1(dp[i],ans);
    }
    cout<<ans;
}

int main(){
    init();
    in();
    solve();
    exit(0);
}