問題
http://topcoder.bgcoder.com/print.php?id=2209
(x,y)座標の点が複数存在し、２人のプレイヤーが交互に選んでいく。
最初は自分からスタートし、選んだ点を赤に塗る。次は相手の番に移り、選んだ点を青に塗る。塗る点がなくなったら終了。
スコアは自分の選んだ点と相手の選んだ点全てに対する距離の差になる。
自分はスコアをできるだけ大きくし、相手はできるだけ少なくする。
このとき、自分が得られる最大のスコアを求める。
解き方
点は１２個と少ないが、自分と相手で戦略が異なるため単純な全探索ではとけない。
そこでｄｐを使い、自分がいままで選んだ点、相手がいままで選んだ点、どちらのターンかを状態に持つ。
自分のターンであればスコアを大きくなる方にＤＦＳを回し、相手のターンであればスコアを小さくなる方にＤＦＳを回せばよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
double p[13][13];
int n;
vector<int> px,py;
map<pair<int,int>,double> m;
class PointsGame {
public:
double f(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double solve(int set1,int set2,int turn){
pair<int,int> cur=make_pair(set1,set2);
if(m.find(cur)!=m.end())return m[cur];
if(set1+set2==((1<<n)-1)){
double sum=0.0;
for(int i=0;i<n;i++){
if(set1&(1<<i)){
for(int j=0;j<n;j++){
if(set2&(1<<j))sum+=p[i][j];
}
}
}
return m[cur]=sum;
}
double ret= (turn==0) ? 0 : 1e+9;
for(int i=0;i<n;i++){
if( !(set1&(1<<i)) && !(set2&(1<<i)) ){
double cost=solve(set2,set1|(1<<i),1-turn);
if(turn==0)ret=max(ret,cost);
else ret=min(ret,cost);
}
}
return m[cur]=ret;
}
double gameValue(vector<int> pointsX, vector<int> pointsY) {
n=pointsX.size();
px=pointsX,py=pointsY;
FORE(i,0,n)FORE(j,0,n)p[i][j]=f(px[i],py[i],px[j],py[j]);
m.clear();
return solve(0,0,0);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
double p[13][13];
int n;
vector<int> px,py;
map<pair<int,int>,double> m;
class PointsGame {
public:
double f(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double solve(int set1,int set2,int turn){
pair<int,int> cur=make_pair(set1,set2);
if(m.find(cur)!=m.end())return m[cur];
if(set1+set2==((1<<n)-1)){
double sum=0.0;
for(int i=0;i<n;i++){
if(set1&(1<<i)){
for(int j=0;j<n;j++){
if(set2&(1<<j))sum+=p[i][j];
}
}
}
return m[cur]=sum;
}
double ret= (turn==0) ? 0 : 1e+9;
for(int i=0;i<n;i++){
if( !(set1&(1<<i)) && !(set2&(1<<i)) ){
double cost=solve(set2,set1|(1<<i),1-turn);
if(turn==0)ret=max(ret,cost);
else ret=min(ret,cost);
}
}
return m[cur]=ret;
}
double gameValue(vector<int> pointsX, vector<int> pointsY) {
n=pointsX.size();
px=pointsX,py=pointsY;
FORE(i,0,n)FORE(j,0,n)p[i][j]=f(px[i],py[i],px[j],py[j]);
m.clear();
return solve(0,0,0);
}
};