bzoj1664[Usaco2006 Open]County Fair Events 参加节日庆祝
题意：
有N个节日，每个节日有个开始时间,及持续时间。牛想尽可能多的参加节日，问最多可以参加多少。注意牛的转移速度是极快的，不花时间，且节日必须完整参加。N≤10000，开始时刻和持续时间≤100000。
题解：
dp。设f[i]表示i时刻到最后时刻最多可以参加多少节日。则f[i]=max(f[i+1],f[range[j].r+1],j为时刻i开始的节日)。
代码：
1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
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