Ski Lessons
动态规划
f[i][j]表示时刻i时滑雪能力为j的前提下，前i个时间单位里最多能滑多少次雪。我们采用向后递推法转移，有三种选择：(1)喝汽水；(2)参加时刻i开始的课程，能力值改变；(3)在能滑的雪坡中选择一个滑。
现在障碍在于雪坡数太多，每次都尝试所有能滑的雪坡转移代价太高。实际上我们并不需要尝试所有能滑的雪坡，因为滑雪用的时间越短越好，而滑任何雪坡效果都是一样的，能滑的雪坡之间没有优劣之分，所以要选择能滑的雪坡中用时最短的那个。通过预处理，可以在常数时间内获取这个信息。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | /* ID: lipeiqi1 LANG: C++ PROB: ski */ #include <iostream> using namespace std; struct tlesson { int start,length,ability; } lesson[10001]; int prev[101][101],mintime[101],f[10001][101]; bool operator<(const tlesson &a,const tlesson &b) { return a.start<b.start; } void update(int &u,int v) { if(u<v) u=v; } int main() { freopen("ski.in","r",stdin); freopen("ski.out","w",stdout); int t,s,n,require,length; scanf("%d%d%d",&t,&s,&n); for(int i=0;i<s;++i) scanf("%d%d%d",&lesson[i].start,&lesson[i].length,&lesson[i].ability); sort(lesson,lesson+s); for(int i=1;i<101;++i) mintime[i]=INT_MAX; for(int i=0;i<n;++i) { scanf("%d%d",&require,&length); for(int j=require;j<101;++j) mintime[j]=min(mintime[j],length); } memset(f,-1,sizeof(f)); f[0][1]=0; int cur=0,ans=-1; for(int i=0;i<=t;++i) { while(cur<s&&lesson[cur].start<i) ++cur; for(int j=1;j<101;++j) if(f[i][j]>-1) { update(ans,f[i][j]); if(i<t) update(f[i+1][j],f[i][j]); if(cur<s&&lesson[cur].start==i&&i+lesson[cur].length<=t) update(f[i+lesson[cur].length][lesson[cur].ability],f[i][j]); if(mintime[j]<INT_MAX&&i+mintime[j]<=t) update(f[i+mintime[j]][j],f[i][j]+1); } } printf("%d\n",ans); return 0; } |