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