問題
複数の（ｘ、ｙ）で表わされる点が与えられる。
各点について、maxPartners以下の次数で結びたい。
また、各点について結ぶ時はminDistance以上の距離がないといけない。
２点間の距離は|x1-x2|+|y1-y2|で表わされる。
このとき、できるだけ多くの点で結びたいときの最終的な結ばれた数と、そのときの最小となる距離の合計を求める。
解き方
点の数は最大１０とのことで、なんとなくビットｄｐが利用できそう。
ただしmaxPartnersは３以下とのことなので単純なビットではいけない。
今回、各点ｄｘの値を次数とした、ｆ（ｄ１、ｄ２、ｄ３）という関数を考える。
この値を減らしていきＤＦＳで探索することで最終的な答えを求めることができる。
ｄｘは最大３となる数であるため、各点ごとに２桁で表わされるビットｄｐを利用する。
コード
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()
int v[1<<(2*10)],m[1<<(2*10)];
class TwinTowns {
public: vector<int> optimalTwinTowns(vector<int> x, vector<int> y, int maxPartners, int minDistance) {
int n=x.size();
memset(v,0,sizeof(v));
memset(m,0,sizeof(m));
FORE(i,0,n){
FORE(j,i+1,n){
int d=abs(x[i]-x[j])+abs(y[i]-y[j]);
if(d>=minDistance){
for(int k=(1<<(2*n))-1;k>=0;k--){
int a=(k>>(2*i))&3,b=(k>>(2*j))&3;
if(a>0&&b>0){
int mask=k-(a<<(2*i))-(b<<(2*j))+((a-1)<<(2*i))+((b-1)<<(2*j));
if(v[k]<v[mask]+1||(v[k]==v[mask]+1&&m[k]>m[mask]+d)){
v[k]=v[mask]+1;
m[k]=m[mask]+d;
}
}
}
}
}
}
vector<int> ret(2,0);
for(int i=0;i<(1<<(2*n));i++){
int ok=1;
FORE(j,0,n)if(((i>>(2*j))&3)>maxPartners)ok=0;
if(ok){
if(ret[0]<v[i]||(ret[0]==v[i]&&ret[1]>m[i])){
ret[0]=v[i];
ret[1]=m[i];
}
}
}
return ret;
}
};
#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()
int v[1<<(2*10)],m[1<<(2*10)];
class TwinTowns {
public: vector<int> optimalTwinTowns(vector<int> x, vector<int> y, int maxPartners, int minDistance) {
int n=x.size();
memset(v,0,sizeof(v));
memset(m,0,sizeof(m));
FORE(i,0,n){
FORE(j,i+1,n){
int d=abs(x[i]-x[j])+abs(y[i]-y[j]);
if(d>=minDistance){
for(int k=(1<<(2*n))-1;k>=0;k--){
int a=(k>>(2*i))&3,b=(k>>(2*j))&3;
if(a>0&&b>0){
int mask=k-(a<<(2*i))-(b<<(2*j))+((a-1)<<(2*i))+((b-1)<<(2*j));
if(v[k]<v[mask]+1||(v[k]==v[mask]+1&&m[k]>m[mask]+d)){
v[k]=v[mask]+1;
m[k]=m[mask]+d;
}
}
}
}
}
}
vector<int> ret(2,0);
for(int i=0;i<(1<<(2*n));i++){
int ok=1;
FORE(j,0,n)if(((i>>(2*j))&3)>maxPartners)ok=0;
if(ok){
if(ret[0]<v[i]||(ret[0]==v[i]&&ret[1]>m[i])){
ret[0]=v[i];
ret[1]=m[i];
}
}
}
return ret;
}
};