luogu P3645 [APIO2015]雅加达的摩天楼

暴力?

暴力!

这个题有点像最短路,所以设\(f_{i,j}\)表示在\(i\)号楼,当前\(doge\)跳跃能力为\(j\)的最短步数,转移要么跳一步到\(f_{i+j,j}\)和\(f_{i-j,j}\),要么换到别的\(doge\),转移到\(f_{i,k}\)

这看似有\(n^2\)的状态,实际上状态数只有\(n\sqrt n\).因为当\(p> \sqrt n\)时,一个\(doge\)只能跳到\(\sqrt n\)个不同的点,这部分为\(m\sqrt n\);当\(p\le \sqrt n\)时,因为\(j\le \sqrt n\),所以总状态数为\(n \sqrt n\).然后是边数,边权只有0/1两种,1边每个状态最多两个,然后0边(也就是换一个\(doge\)),显然对于每个\(i\)只用在\(f_{i,j}\)最小的状态转移更优,所以转移总数也是\(n\sqrt n\)的

实现的话可以用双端队列实现0/1最短路.另外还需要判断一个状态是否访问过,\(30000*30000\)的\(bool\)数组开不下,所以可以\(bitset\)

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db double

using namespace std;

const int N=30000+10;

int rd()

{

	int x=0,w=1;char ch=0;

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

	return x*w;

}

bitset<N> v[N];

int n,m,ps,ans=1<<30;

vector<int> dog[N];

struct node

{

	int x,j,d;

};

deque<node> q;

int main()

{

	n=rd(),m=rd();

	int b=rd()+1,p=rd();

	v[b][p]=1,q.push_front((node){b,p,0});

	for(int i=1;i<m;++i)

	{

		b=rd()+1,p=rd();

		if(i==1) ps=b;

		dog[b].push_back(p);

	}

	while(!q.empty())

	{

		int x=q.front().x,j=q.front().j,d=q.front().d;

		q.pop_front();

		if(x==ps) ans=min(ans,d);

		vector<int>::iterator it;

		for(it=dog[x].begin();it!=dog[x].end();++it)

		{

			int y=*it;

			if(!v[x][y]) v[x][y]=1,q.push_front((node){x,y,d});

		}

		dog[x].clear();

		if(x-j>=1&&!v[x-j][j]) v[x-j][j]=1,q.push_back((node){x-j,j,d+1});

		if(x+j<=n&&!v[x+j][j]) v[x+j][j]=1,q.push_back((node){x+j,j,d+1});

	}

	printf("%d\n",ans<(1<<30)?ans:-1);

	return 0;

}

巴特西

luogu P3645 [APIO2015]雅加达的摩天楼

最新文章

热门文章