题解 P2948 【[USACO09OPEN]滑雪课Ski Lessons】

正常的DP。考虑这样两个东西：如果我们有两天能力值相同的坡，那么我们选时间短的坡更优；如果我们有结束时间相同的课程（从DP反向看），那么我们选择开始时间最晚的那一门。 维护上面那段话说的玩意，以下代码中即为c和classes。 然后再维护一下每个时间的能力最大值，记为d，初始为1，然后被上课更新，只有枚举的能力值小于这个值才可以滑雪。 用dp[I][j]表示在I的时间时，所拥有j的能力值的时候的最大滑雪次数 考虑喝可可:直接就是上一次的数据dp[I][j]=dp[I-1][j]; 考虑上课:由于能力值增加，所以更新d，然后滑雪次数继承上课开始时间的所有能力值对应的滑雪次数的最大值（这里可以开一个maxn数组记录一下，答案也可以直接从这里找）; 考虑滑雪:当然是能滑就滑呀，然后滑雪次数继承开始滑雪时间的当前能力值对应的滑雪次数的最大值。 ```cpp #include<cstdio> #include<cctype> #include<cstring> #include<algorithm> using namespace std; inline char get_char(){//劲者快读 static char buf[1000001],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline short read(){ short num=0; char c; while(isspace(c=get_char())); while(num=num*10+c-48,isdigit(c=get_char())); return num; } int dp[10001][101],classes[20002][101]; int c[101],maxn[10001]; int t,s,n; int main(){ t=read(),s=read(),n=read(); for(int i=1;i<=s;i++){ int m=read(),l=read(),a=read(); if(classes[m+l-1][a]<m) classes[m+l-1][a]=m;//注意时间算法 } fill(c,c+101,10001);//初始化最短坡 for(int i=1;i<=n;i++)//注意重复的时候选最小值 for(int j=read(),ds=read();j<=100;j++) if(c[j]>ds) c[j]=ds;//记录每个能力值下的最短坡 for(int i=1,d=1;i<=t;i++){//d记录当前最大能力值 for(int j=1;j<=100;j++){ dp[i][j]=dp[i-1][j];//喝可可 if(classes[i-1][j]&&dp[i][j]<maxn[classes[i-1][j]]) dp[i][j]=maxn[classes[i-1][j]],d=max(d,j);//向前追溯上课时间 if(i>=c[j]&&j<=d&&dp[i][j]<dp[i-c[j]][j]+1) dp[i][j]=dp[i-c[j]][j]+1;//滑雪 if(maxn[i]<dp[i][j]) maxn[i]=dp[i][j];//记录时间上的最优解使classes允许调用 } } printf("%d",maxn[t]); return 0; } ```