E. Ski Lessons (DP)
題意:
滑雪場有N(N<=10000)種項目, 可以從任意時刻開始, 可以反復參加. 每種項目要求參與者技能值(<=100)至少為c[i], 耗費連續的d[i]單位時間.
此外,滑雪場提供S(S<=100)個培訓課程. 每個課程開始時間為m[i], 持續時間l[i], 結束后, 參加者的技能值變為a[i]. 如果選擇參加某個課程,不能遲到早退. 只能同時參加一個課程.
一個人在任意時刻只能做一件事, 而且他總共有 T(T<=10000) 單位時間. 他必須在時刻T結束所有活動.
問如何安排可以使得此人參加最多次滑雪項目, 求最大次數.
解:
O(100*N)預處理, len[i][j]表示技能值為i時, 參加一次任意項目的最短時間.
O(S*S)DP, dp[i]表示在課程i開始的前一時刻, 已參加項目的最大次數.
注意到, 結束一項課程后人的技能值是一定的. 因此, 可以枚舉參加i之前最近參加的課程k, 兩次課程之間的收益可直接計算. 則dp[i] = max(dp[k]+ (m[i]-m[k]-l[k])/len[a[k]]).
posted on 2009-06-29 22:11
wolf5x 閱讀(134)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc