poj 1764 Dice Contest

首先我要吐槽这个题目描述不清。\(2\)对着选手，那选手朝那边？看完别人写的程序后我才知道选手对着目标所在的方向（或左或右）。

然后这道题还是不错的，因为他交给我矩阵乘法不只有常规意义下的矩阵乘法，只要满足结合律，取 \(\min\) 都行。涨姿势了。

这题我们这么做，我们用\(f[i][j][k]\)表示骰子从起始位置到\((i,j)\)且最后状态为\(k\)所需要最小代价，类似于最短路。然后直接求肯定gg，肯定是要用矩阵乘法来加速。

考虑到\(y\)的范围只有\(4\)，我们可以将后两维压成一维，就设为\(g[i][j]\)吧。如果我们能够知道第\(i\)列的所有状态到第\(i+1\)列的所有状态的最短路，(设第\((i,j)\)到\((i+1,k)\)的最小代价为\(h[1][j][k]\))，那么我们就可以知道第\(i\)列所有状态到\(i+n(n>1)\)列所有状态的最小代价了(设第\((i,j)\)到\((i+n,k)\)的最小代价为\(h[n][j][k]\))。则

\[h[n][i][j] = \min \{ h[n-1][i][k]+h[1][k][j] \}
\]

然后这个式子很像矩阵乘法的式子(把和改成了\(\min\))，然后满足结合律，故也可用矩阵乘法来加速。

那么怎么求\(h[1][i][j]\)呢？我们可以将列限制在一个范围内，然后跑最短路就行了。

这个题目最坑爹的地方就是状态处理，这个可以参见std。

#include<queue>

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

typedef long long ll;

const int Ex = 20,maxn = Ex*96*5; const ll inf = 1LL<<60;

const int help[6][6] = {{-1,2,4,1,3,-1},{3,-1,0,5,-1,2},{1,5,-1,-1,0,4},{4,0,-1,-1,5,1},{2,-1,5,0,-1,3},{-1,3,1,4,2,-1}};

int L[6],X1,Y1,X2,Y2,side[maxn],toit[maxn],next[maxn],len[maxn],cnt; ll dis[Ex*97],f[100],g[100][100]; bool in[Ex*97];

struct Matrix

{

	int N,M; ll S[96][96];

	inline Matrix(int n = 0,int m = 0,bool sign = false):N(n),M(m)

	{

		for (int i = 0;i < n;++i) for (int j = 0;j < m;++j) S[i][j] = inf;

		if (sign) for (int i = 0;i < n;++i) S[i][i] = 0;

	}

	friend inline Matrix operator*(const Matrix &a,const Matrix &b)

	{

		Matrix c(a.N,b.M);

		for (int i = 0;i < c.N;++i)

			for (int j = 0;j < c.M;++j)

				for (int k = 0;k < a.M;++k)

					c.S[i][j] = min(c.S[i][j],a.S[i][k]+b.S[k][j]);

		return c;

	}

};

inline void add(int a,int b,int c) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; len[cnt] = c; }

inline int getid(int x,int y,int top,int front)

{

	int front_id = -1;

	for (int i = 0;i < 6;++i)

	{

		if (i != top&&i != 5-top) ++front_id;

		if (i == front) return x*96+y*24+top*4+front_id;

	}

	return -1;

}

inline void ready()

{

	for (int x = 0;x < Ex;++x)

		for (int y = 0;y < 4;++y)

			for (int top = 0;top < 6;++top)

				for (int front = 0;front < 6;++front)

				{

					if (front == top||front == 5-top) continue;

					int left = help[top][front],u = getid(x,y,top,front);

					int nx,ny,ntop,nfront,v;

					if (x)

					{

						nx = x-1; ny = y; ntop = 5-left; nfront = front;

						v = getid(nx,ny,ntop,nfront); add(u,v,L[ntop]);

					}

					if (x+1 < Ex)

					{

						nx = x+1; ny = y; ntop = left; nfront = front;

						v = getid(nx,ny,ntop,nfront); add(u,v,L[ntop]);

					}

					if (y)

					{

						nx = x; ny = y-1; ntop = 5-front; nfront = top;

						v = getid(nx,ny,ntop,nfront); add(u,v,L[ntop]);

					}

					if (y < 3)

					{

						nx = x; ny = y+1; ntop = front; nfront = 5-top;

						v = getid(nx,ny,ntop,nfront); add(u,v,L[ntop]);

					}

				}

}

inline void spfa(int source)

{

	queue <int> team;

	for (int i = 0;i < Ex*96;++i) dis[i] = inf;

	dis[source] = 0; in[source] = true; team.push(source);

	while (!team.empty())

	{

		int now = team.front(); team.pop();

		for (int i = side[now];i;i = next[i])

		{

			if (dis[toit[i]] <= dis[now]+len[i]) continue;

			dis[toit[i]] = dis[now]+len[i];

			if (!in[toit[i]]) team.push(toit[i]),in[toit[i]] = true;

		}

		in[now] = false;

	}

}

inline void record(int x,ll A[])

{

	for (int y = 0;y < 4;++y)

		for (int top = 0;top < 6;++top)

			for (int front = 0;front < 6;++front)

			{

				if (front == top||front == 5-top) continue;

				int id = getid(x,y,top,front); A[id%96] = dis[id];

			}

}

inline Matrix qsm(Matrix a,int b)

{

	Matrix ret(96,96,true);

	for (;b;b >>= 1,a = a*a) if (b&1) ret = ret*a;

	return ret;

}

inline ll work()

{

	int diff = abs(X1-X2),x = Ex >> 1; ll ans = inf;

	spfa(getid(x,Y1,0,1));

	if (!diff)

	{

		for (int top = 0;top < 6;++top)

			for (int front = 0;front < 6;++front)

			{

				if (front == top||front == 5-top) continue;

				ans = min(ans,dis[getid(x,Y2,top,front)]);

			}

		return ans;

	}

	record(x,f);

	for (int y = 0;y < 4;++y)

		for (int top = 0;top < 6;++top)

			for (int front = 0;front < 6;++front)

			{

				if (front == top||front == 5-top) continue;

				int source = getid(x,y,top,front);

				spfa(source); record(x+1,g[source%96]);

			}

	Matrix A(96,96);

	for (int i = 0;i < 96;++i) for (int j = 0;j < 96;++j) A.S[i][j] = g[i][j];

	A = qsm(A,diff);

	for (int i = 0;i < 96;++i)

		for (int j = 0;j < 96;++j)

			if (j/24 == Y2) ans = min(ans,f[i]+A.S[i][j]);

	return ans;

}

int main()

{

	freopen("1764.in","r",stdin);

	freopen("1764.out","w",stdout);

	for (int i = 0;i < 6;++i) scanf("%d",L+i);

	scanf("%d %d %d %d",&X1,&Y1,&X2,&Y2); --Y1,--Y2;

	if (X1 > X2) swap(L[2],L[3]);

	ready();

	cout << work() << endl;

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

poj 1764 Dice Contest

最新文章

热门文章