TopCoder SRM 340 Div1 Medium CsCourses
問題
授業がn個ある。
それぞれ、三つの値theoreticalValue[i], practicalValue[i], expire[i]が定められている。
最初、theoretical, practicalの値は0で、
授業を取ると、theoreticalがtheoreticalValue[i]の値まで上がり、
theoreticalがpracticalValue[i]の値まで上がる。(値の低い授業をとっても下がることはない)
授業は一月に1個しかとることができない。
また、theoreticalがtheoreticalValue[i]-1以上で、practicalがpracticalValue[i]-1以上の授業しか取ることができない。
授業には期限があり、それぞれの授業はexpire[i]か月目以内に取らなければならない。
このとき、theoretical, practicalの値をともにskillBound以上にするために取る、
最小の授業の数、およびその授業の番号を求めよ。
授業の番号は、取り方が複数個ある場合は辞書順で最小のものを求めよ。
制約条件
n≦50
theoreticalValue[i], practicalValue[i], expire[i]≦50
方針
動的計画法+経路復元
dp[m][t][p]を、mヶ月目までで、theoreticalがt, practicalがpであるような状態から、
あと何ヶ月でt,pがskillBound以上になるかの最小の月数とする。
これを更新していくようなDPにより解ける。
経路復元が必要なので、使った授業を覚えておく。
ソースコード
vi tv, pv, e; int n, b; int dp[51][51][51], next[51][51][51]; int rec(int m,int t,int p){ int &res=dp[m][t][p]; if(res>=0)return res; if(t>=b&&p>=b)return res=0; if(m>=n)return res=inf; res=inf; rep(i,n)if(t>=tv[i]-1&&p>=pv[i]-1&&m<e[i]){ int nt=max(t,tv[i]), np=max(p,pv[i]); int tmp=rec(m+1,nt,np)+1; if(tmp<res)res=tmp, next[m][t][p]=i; } return res; } class CsCourses { public: vector <int> getOrder(vector <int> theoreticalValue, vector <int> practicalValue, vector <int> expire, int skillBound) { tv=theoreticalValue; pv=practicalValue; e=expire; b=skillBound; n=e.size(); memset(dp,-1,sizeof(dp)); if(rec(0,0,0)==inf)return vi(0); vi ans; int t=0, p=0, m=0; while(t<b||p<b){ ans.pb(next[m][t][p]); int nt=max(t,tv[next[m][t][p]]), np=max(p,pv[next[m][t][p]]); m++; t=nt; p=np; } return ans; } };