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;
	}
};