SRM320 div1 medium

メモ化再帰するだけ。

#include <sstream>
#include <vector>

using namespace std;

class ContestSchedule
{
	public:

		int n;
		double cache[55];
		vector<int> start;
		vector<int> end;
		vector<double> winExp;

		double rec(int lastContest)
		{
			double &r=cache[lastContest];
			if(!(r<0))
				return r;

			r=0.0;
			for(int i=0;i<n;i++)
				if(end[lastContest]<=start[i])
					r=max(r,winExp[i]+rec(i));
			return r;
		}

		double expectedWinnings(vector<string> contests)
		{
			contests.push_back("-1 0 0");
			n=contests.size();
			for(int i=0;i<n;i++)
			{
				cache[i]=-1.0;
				stringstream ss(contests[i]);
				int s,e;
				double w;
				ss >> s >> e >> w;
				w/=100.0;
				start.push_back(s);
				end.push_back(e);
				winExp.push_back(w);
			}

			return rec(n-1);
		}
};