多米诺骨牌

Description

多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。

Analysis

题目大意为求状态a到达状态b的最短路径，只不过状态b不是一个固定值。可以使用dp[i][j]表示前i个方块到达差值j的最小旋转次数。因为差值有两种情况：上面大和下面大。所以在dp数组再加一维，dp[i][j][f]，f表示上下大小关系。最后在dp[n][j]中选择j最小的可行状态输出。

对于第i个骨牌，上下之间的差为dis，先讨论dis>0的转移方式：

1. 不旋转，则旋转次数由dp[i][j-dis]继承而来
2. 旋转，则旋转次数为dp[i][j+dis]+1

其中因为j-dis不能小于0，所以要适当调控第三维。dis<0时同理反之。

Code

#include <bits/stdc++.h>
#define MAXN 5000

int n,ans,u[1001],d[1001],dis[1001],opt[1001][5001][2];

int main()
{
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	std::cin>>n;
	for(int i=1;i<=n;i++)
		std::cin>>u[i]>>d[i],dis[i]=u[i]-d[i];
	memset(opt,0x3f,sizeof(opt));
	opt[0][0][0]=opt[0][0][1]=0;
	for(int i=1;i<=n;i++)
		for(int j=MAXN;j>=0;j--)
		{
			if(j-dis[i]>=0)
			{
				opt[i][j][0]=opt[i-1][j-dis[i]][0];
				opt[i][j][1]=opt[i-1][j-dis[i]][1]+1;
			}
			if(j+dis[i]>=0)
			{
				opt[i][j][0]=std::min(opt[i][j][0],opt[i-1][j+dis[i]][0]+1);
				opt[i][j][1]=std::min(opt[i][j][1],opt[i-1][j+dis[i]][1]);
			}
			if(j-dis[i]<=0)
			{
				opt[i][j][0]=std::min(opt[i][j][0],opt[i-1][dis[i]-j][1]);
				opt[i][j][1]=std::min(opt[i][j][1],opt[i-1][dis[i]-j][0]+1);
			}
			if(j+dis[i]<=0)
			{
				opt[i][j][0]=std::min(opt[i][j][0],opt[i-1][-dis[i]-j][1]+1);
				opt[i][j][1]=std::min(opt[i][j][1],opt[i-1][-dis[i]-j][0]);
			}
		}
	for(int i=0;i<=MAXN;i++)
	{
		int res=std::min(opt[n][i][0],opt[n][i][1]);
		if(res<0x3f3f3f3f)
		{
			std::cout<<res<<std::endl;
			break;
		}
	}
	return 0;
}