题解 P1803 【凌乱的yyy】

Running_Coder · 2017-04-13 22:34:20 · 题解

看到好多大佬用贪心。。。表示萌新老老实实用的DP

进入正题：

定义f[i]表示在前[i]场比赛中最多可以参加几场比赛，

由此得出方程：f[i]=max(f[i-1],f[temp]+1);

f[temp]指从f[i-1]向前找到的第一个允许参加第i场比赛的f[]

由于每次循环时都向前找一次temp会浪费太多时间，又因为f[]是单调递增的，

故可以令temp在循环时逐步递增，这样时间复杂度就降到了O(n).

代码如下：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std; 
struct qj{
    int l,r;
};
bool cmp(qj a,qj b){
    if(a.r!=b.r)return a.r<b.r;
    return a.l<b.l;
}
qj game[1000005];
int f[1000005];
int i,n,temp;
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&game[i].l,&game[i].r);  
    sort(game+1,game+1+n,cmp);
    f[0]=0;
    temp=0;
    for(i=1;i<=n;i++){
        while(game[temp+1].r<=game[i].l)temp++;
        f[i]=max(f[i-1],f[temp]+1);
    }
    printf("%d\n",f[n]);
    return 0;
}