Farmer John 想要带着 Bessie 一起在科罗拉多州一起滑雪。很不幸，Bessie滑雪技术并不精湛。 Bessie了解到，在滑雪场里，每天会提供S(0<=S<=100)门滑雪课。第i节课始于M_i(1<=M_i<=10000),上的时间为L_i(1<=L_i<=10000)。上完第i节课后，Bessie的滑雪能力会变成A_i(1<=A_i<=100). 注意：这个能力是绝对的，不是能力的增长值。 Bessie买了一张地图，地图上显示了N(1 <= N <= 10,000)个可供滑雪的斜坡，从第i个斜坡的顶端滑至底部所需的时长D_i(1<=D_i<=10000)，以及每个斜坡所需要的滑雪能力C_i(1<=C_i<=100)，以保证滑雪的安全性。Bessie的能力必须大于等于这个等级，以使得她能够安全滑下。 Bessie可以用她的时间来滑雪，上课，或者美美地喝上一杯可可汁，但是她必须在T(1<=T<=10000)时刻离开滑雪场。这意味着她必须在T时刻之前完成最后一次滑雪。 求Bessie在实现内最多可以完成多少次滑雪。这一天开始的时候，她的滑雪能力为1.
第1行：3个用空格隔开的整数：T, S, N。
第2~S+1行:第i+1行用3个空格隔开的整数来描述编号为i的滑雪课：M_i,L_i,A_i。
第S+2~S+N+1行：
第S+i+1行用2个空格隔开的整数来描述第i个滑雪坡：C_i,D_i。
一个整数，表示Bessie在时间限制内最多可以完成多少次滑雪。
滑第二个滑雪坡1次，然后上课，接着滑5次第一个滑雪坡。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R i=a;i<=b;i++) 5 #define Rep(i,a,b) for(R i=a;i>=b;i--) 6 #define ms(i,a) memset(a,i,sizeof(a)) 7 #define gc() getchar() 8 template<class T>void read(T &x){ 9 x=0; char c=0; 10 while (!isdigit(c)) c=gc(); 11 while (isdigit(c)) x=x*10+(c^48),c=gc(); 12 } 13 int const N=10000+3; 14 int const M=100+3; 15 int const inf=1e8; 16 struct Edge{ 17 int to,nt,w; 18 }E[M]; 19 int cnt,H[N],t,s,n,c[N],d[N],f[N][M],g[M]; 20 void add(int a,int b,int c){ 21 E[cnt]=(Edge){b,H[a],c}; H[a]=cnt++; 22 } 23 int main(){ 24 read(t); read(s) ;read(n); 25 ms(-1,H); 26 while (s--){ 27 int x,y,z; 28 read(x); read(y); read(z); 29 add(x,x+y,z); 30 } 31 rep(i,0,100) g[i]=inf; 32 rep(i,1,n) read(c[i]),read(d[i]),g[c[i]]=min(g[c[i]],d[i]); 33 rep(i,1,100) g[i]=min(g[i],g[i-1]); 34 ms(-1,f); 35 f[0][1]=0; 36 rep(i,0,t)rep(j,1,100) if(f[i][j]>-1) { 37 f[i+1][j]=max(f[i+1][j],f[i][j]); 38 for(R k=H[i];k!=-1;k=E[k].nt){ 39 int v=E[k].to; 40 if(E[k].w<=j) continue; 41 if(v>t) continue; 42 f[v][E[k].w]=max(f[v][E[k].w],f[i][j]); 43 } 44 if(i+g[j]<=t) f[i+g[j]][j]=max(f[i+g[j]][j],f[i][j]+1); 45 } 46 int ans=0; 47 rep(i,0,100) ans=max(ans,f[t][i]); 48 cout<<ans<<endl; 49 return 0; 50 }
bzoj 1571 [Usaco2009 Open]滑雪课Ski
原文：https://www.cnblogs.com/ZJXXCN/p/10559618.html
