SRM486 div1 medium

どっかでやったことがあるような気がする。
メモ化再帰。

#include <vector>
#include <map>

using namespace std;

class QuickSort 
{
	public:

		map<vector<int>,double> cache;

		double rec(vector<int> L)
		{
			double r;
			if(L.size()<2)
				r=0.0;
			else if(cache.find(L)!=cache.end())
				return cache[L];
			else
			{
				r=0.0;
				int n=L.size();
				for(int i=0;i<n;i++)
				{
					vector<int> left,right;
					for(int j=0;j<n;j++)
					{
						if(L[j]<L[i])
						{
							left.push_back(L[j]);
							if(i<j)
								r+=1.0/(double)n;
						}
						if(L[i]<L[j])
						{
							right.push_back(L[j]);
							if(j<i)
								r+=1.0/(double)n;
						}
					}
					r+=(rec(left)+rec(right))/(double)n;
				}
			}
			return cache[L]=r;
		}

		double getEval(vector <int> L) 
		{
			return rec(L);
		}
};