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