题意：

有N个节日，每个节日有个开始时间,及持续时间。牛想尽可能多的参加节日，问最多可以参加多少。注意牛的转移速度是极快的，不花时间，且节日必须完整参加。N≤10000，开始时刻和持续时间≤100000。

题解：

dp。设f[i]表示i时刻到最后时刻最多可以参加多少节日。则f[i]=max(f[i+1],f[range[j].r+1],j为时刻i开始的节日)。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define maxn 10100 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 using namespace std; 7  8 inline int read(){ 9     char ch=getchar(); int f=1,x=0;10     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();12     return f*x;13 }14 struct rg{
   int len,n;}; rg rgs[maxn]; int f[maxn*20],n,mx,g[maxn*20];15 int main(){16     n=read(); inc(i,1,n){
   int a=read(),b=read(); rgs[i]=(rg){b,g[a]}; g[a]=i; mx=max(mx,a);}17     for(int i=mx;i>=1;i--){18         f[i]=f[i+1]; for(int j=g[i];j;j=rgs[j].n)f[i]=max(f[i],f[i+rgs[j].len]+1);19     }20     printf("%d",f[1]); return 0;21 }
       
      
     

 

20160730