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

ICPC North Central NA Contest 2017 B - Pokemon Go Go

边霄
2023-12-01

DOOOR

赤裸裸的状鸭TSP
就是在设计状态的时候纠结了一下,到底鸭个数还是种类数?
好吧,目(mú)标意识又没(mēi)有啦
目标在哪里捏?收集全部种类的宝可梦!
所以这么想的话世界突然就明亮了:
不用一顿乱check,只用枚举一下每种宝可梦的每个宝可梦的位置就行了!
第二维如果表示种数的话,方程列不出来,因为不知道抓的上一种在哪个位置,无法计算这次抓走的距离

然鹅,从(0,0)开始

写完了才发现!!!!!

所以怎么处理!!!!
枚举第一个抓的和最后一个抓的,取min{dis((0,0)->first)+dp[E][last]+dis(last->(0,0))}
然鹅犯傻了的我当时竟然想歪了??
把(0,0)当第一种宝可梦。。。
然后就不知到怎么的调了半天

//B2
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int dp[1<<16][22],d[22],n,mind=INF;
int nkind,kind[24];
vector<int>ve[20];
map<string,int>mp;
inline bool check(int i,int j,int k) {
	if(!(i&d[kind[j]]))return 0;//这种没有走过
	if(i&d[kind[k]])return 0;//要抓的那个的属性种已经去过
	return 1;
}
struct node{
    int x,y;
}pos[24];
int dis(int u,int v){
    return abs(pos[u].x-pos[v].x)+abs(pos[u].y-pos[v].y);
}
int main() {
	cin>>n;
    n++;
    string s;
    nkind=1;
    ve[1].push_back(1);
    kind[1]=1;
    mp["0"]=1;
    for(int i=2;i<=n;i++){
        cin>>pos[i].x>>pos[i].y>>s;
        if(!mp[s])nkind++,mp[s]=nkind;
        kind[i]=mp[s];
        ve[kind[i]].push_back(i);
        }
    
	//最终状态,第1到n位全都为1 
	d[1]=1; 
    int E=(1<<nkind)-1;
	//i=2!!!!
	for(int i=2; i<=nkind; i++)d[i]=(d[i-1]<<1);//从1到n,位数为i的二进制值  1 10 100 1000 10000,后面取用 
	for(int i=0; i<=E; i++)
		for(int j=1; j<=n; j++)dp[i][j]=INF;//初始化状态数组 
	dp[1][1]=0;

	for(int i=1; i<=E; i++)
		for(int j=1; j<=n; j++)//枚举最后到的点 
			for(int k=1; k<=n; k++) {//枚举将要到的点 
				if(check(i,j,k)) {//可以走, 
                    for(int v=0;v<ve[kind[j]].size();v++){
                  
                      dp[i + d[kind[k]]][k] =
                          min(dp[i + d[kind[k]]][k],
                              dp[i][ve[kind[j]][v]] +dis(ve[kind[j]][v], k));
                 
                    }
				}
        }
	for(int i=2;i<=nkind;i++){
        for(int v=0;v<ve[i].size();v++)
          mind = min(mind, dp[E][ve[i][v]] + dis(ve[i][v], 1))
    }
	cout<<mind;
	return 0;
}


 类似资料:

相关阅读

相关文章

相关问答