当前位置: 首页 > 工具软件 > PokemonGo Map > 使用案例 >

ICPC North Central NA Contest 2017 B题 Pokemon Go Go(状压dp)

胡俊弼
2023-12-01

题目链接:Pokemon Go Go

题目大意:
一个抓宝可梦的游戏,玩家一开始站在(0, 0)点,接着输入n表示宝可梦的数量,接着输入n行,每行两个整数和一个字符串,表示这个种类的宝可梦以及当前这只所在的坐标(这n只里面可能有好几只同种的宝可梦在不同位置)。
题目问玩家从(0, 0)开始,只能上下左右走,要把每种宝可梦都抓到一只且仅一只,最后回到(0, 0),最短的路程是多少。
样例输入
5
5 9 Eevee
20 20 Flareon
1 1 Flareon
1 8 Jolteon
2 8 Umbreon
样例输出
28
样例解释:
The distance from (0,0) to (5,9) is 14
The distance from (5,9) to (2,8) is 4
The distance from (2,8) to (1,8) is 1
The distance from (1,8) to (1,1) is 7
The distance from (1,1) to (0,0) is 2

思路: n最大是25,宝可梦的种类最多就15,一个整数即可表示目前抓到的宝可梦集合的状态,因此可以状压dp。按状压dp的套路,其中一个参数是状压的整数,另一个则是最后加入这个集合中的宝可梦的编号。
所以 dp[i][j] 表示当前抓的宝可梦的集合是 i ,最新一只抓到的是第 j 只。
(P.S. 这里的 j 表示的是【第 j 只】,而不是【第 j 种】,这题宝可梦有两个编号,一个是在地图中的编号,一个是所属种类的编号,j 是取于前者而不是后者。我一开始做这题时用了后者,最后发现难以处理同一种宝可梦取哪只的问题)
为了实现每种宝可梦只抓一只,我们需要处理个体id和种类id的映射关系,在输入时记录每个个体的id,即0~n-1,以及每个个体的种类,即type[i]表示第 i 个个体的种类。
· 然后开始写dp的部分,dp数组表示的是距离,一开始可以直接算出的是,只抓了一只的情况的dp值,即原点到这只的距离。其他都设为INF。
接着枚举集合 i ,从1到全1。再枚举 i 集合中最新抓的一只 j ,去掉它,得到集合last,表示上一个状态,为了确定上一个状态last的值还要枚举出last中最新抓的一只 k。当前和上一状态就确定了,
然后状态转移:dp[i][j] = min(dp[i][j], dp[last][k] + cal(k, j));
· 由于最后要求玩家还要回到原点,我一开始的想法是人为加一只宝可梦在(0, 0)参与递推,但是还得考虑它得是最后一个被抓的,比较麻烦,于是发现这个放在递推循环外也是等价的。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct node{
	int x, y;
};
node pokemons[30];
int type[30];	//	第i只的种类
unordered_map<string, int> mp;
int n, id = 0;
int dp[(1 << 17)][30];
string s;

inline int cal(int a, int b){
	return abs(pokemons[a].x- pokemons[b].x) + abs(pokemons[a].y- pokemons[b].y);
}

int main(){
	cin >> n;
	for(int i = 0; i < n; ++i){
		int r, c;
		cin >> r >> c >> s;
		if(mp[s] == 0){
			type[i] = ++id;
			mp[s] = id;
			pokemons[i] = node{r, c};
		}
		else{
			type[i] = mp[s];
			pokemons[i] = node{r, c};
		}
	}
	memset(dp, 0x3f, sizeof dp);
	for(int i = 0; i < n; ++i){
		dp[1<<(type[i]-1)][i] = cal(n+3, i);// pokemon[n+3]没初始化过,表示(0, 0)点
	}
	int limit = (1 << id) - 1;
	for(int i = 1; i <= limit; ++i){	//	集合状态
		if(i == (i & (-i)))	//	只抓了一只的情况初始化过了,用lowbit的方法判断然后跳过
			continue;
		for(int j = 0; j < n; ++j){	//	当前删去的点在集合的位置
			if(!(i & (1 << (type[j]-1))))
				continue;
			int last = i - (1 << (type[j]-1));	//	last是当前状态去掉j号的状态
			for(int k = 0; k < n; ++k){	//	last上次走的点是k号
				if(last & (1 << (type[k]-1))){
					dp[i][j] = min(dp[i][j], dp[last][k] + cal(k, j));
				}
			}
		}
	}
	int ans = 0x3f3f3f3f;
	for(int i = 0; i < n; ++i)
		ans = min(ans, dp[limit][i] + cal(n+3, i));
	cout << ans << endl;

	return 0;
}
 类似资料: