PokemonGoGo(状压dp)

//捕捉宝可梦
//考虑状压dp，一维是宝可梦的捕捉状态，二维保存当前捕捉的宝可梦编号
const int inf = 0x3f3f3f3f;
int n, cnt;
int dp[1 <<20][22];//dp[sta][point]
unordered_map mp;
struct point {
int x, y;
int type;
};
point a[25];
string s;
int get_cal(point i, point j) {
return abs(i.x - j.x) + abs(i.y - j.y);
}
int main() {
ios::sync_with_stdio(0);
while (cin >> n) {
for (int i = 0; i cin >> a[i].x >> a[i].y;
cin >> s;
if (!mp.count(s)) mp[s] = cnt++;
a[i].type = mp[s];
}
memset(dp, inf, sizeof dp);
for (int i = 0; i dp[(1 < }
int limit = (1 < for (int i = 0; i if ((i == (i & -i))) continue;//已经初始化，跳过
for (int j = 0; j if (!(i & (1 < int last = i - (1 < for (int k = 0; k if (last & (1 < }
}
}
int ans = inf;
for (int i = 0; i ans = min(ans, dp[limit - 1][i] + get_cal(a[n + 3], a[i]));//a[n+3]未初始化，为(0,0)
cout < }
return 0;
}