SRM407 div1 medium

map,得点>でメモ化再帰。
どちらの番かという情報は”どの頂点が残っている”から得ることができる。

#include <map>
#include <vector>
#include <float.h>
#include <cmath>

using namespace std;

int n;
double point[(1<<13)];
map<int,double> cache;

int popCount(int _mask)
{
	int r=0;
	for(int i=0;i<28;i++)
		if(_mask & (1<<i))
			r++;
	return r;
}

double rec(int left,int red)
{
	int key=(left<<13)+red;

	if(cache.find(key)!=cache.end())
		return cache[key];
	else if(left==0)
		return cache[key]=point[red];
	else
	{
		int turn=n-popCount(left);
		if(turn%2==0)
		{
			double r=-10.0;
			for(int i=0;i<n;i++)
				if(left&(1<<i))
					r=max(r,rec(left^(1<<i),red));
			return cache[key]=r;
		}
		else
		{
			double r=DBL_MAX;
			for(int i=0;i<n;i++)
				if(left&(1<<i))
					r=min(r,rec(left^(1<<i),red^(1<<i)));
			return cache[key]=r;
		}
	}
}

class PointsGame 
{
	public:


		double gameValue(vector <int> pointsX, vector <int> pointsY) 
		{
			n=pointsX.size();
			cache.clear();
			for(int red=0;red<(1<<n);red++)
				if(popCount(red)==(n+1)/2)
				{
					point[red]=0.0;
					for(int i=0;i<n;i++)
						for(int j=i+1;j<n;j++)
							if((0<(red&(1<<i)))^(0<(red&(1<<j))))
							{
								double xd=pointsX[i]-pointsX[j];
								double yd=pointsY[i]-pointsY[j];
								point[red]+=sqrt(xd*xd+yd*yd);
							}
				}

			return rec((1<<n)-1,(1<<n)-1);
		}
};