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