多米诺骨牌有上下2个方块组成,每个方块中有1~6个点。现有排成行的
上方块中点数之和记为S1,下方块中点数之和记为S2,它们的差为|S1-S2|。例如在图8-1中,S1=6+1+1+1=9,S2=1+5+3+2=11,|S1-S2|=2。每个多米诺骨牌可以旋转180°,使得上下两个方块互换位置。 编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小.

对于图中的例子(图挂了看luogu),只要将最后一个多米诺骨牌旋转180°,可使上下2行点数之差为0

设计状态f[n][k]为前n个骨牌翻转达到 上sum-下sum=k的最少翻转次数
则根据规则,第i个牌可以翻转或不翻转,

dp[i][k+upx[i]-downx[i]]=min(dp[i-1][j+5000],dp[i][k+upx[i]-downx[i]]);  //不翻转
dp[i][k-upx[i]+downx[i]]=min(dp[i-1][j+5000]+1,dp[i][k-upx[i]+downx[i]]); //翻转

最后找差值最小就行了,注意考虑对称
else if (minx==abs(i-5000)) ans=min(dp[n][i],dp[n][rever]);

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
using namespace std;
int n,upx[1010]={0},downx[1010]={0},dp[1010][10010]={0};
int minx=0,ans=0,rever=0;
int main()
{
	memset(dp,0x3f,sizeof(dp));
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&upx[i],&downx[i]);
	
	dp[0][5000]=0;
	
	for (int i=1;i<=n;i++)
	{
		for (int j=0-(n*5);j<=n*5;j++)
		{
			dp[i][j+5000+upx[i]-downx[i]]=min(dp[i-1][j+5000],dp[i][j+5000+upx[i]-downx[i]]);
			dp[i][j+5000-upx[i]+downx[i]]=min(dp[i-1][j+5000]+1,dp[i][j+5000-upx[i]+downx[i]]);
		}
	}
	
	minx=dp[0][0];
	
	for (int i=5000-5*n;i<=5000+5*n;i++)
	{
		if (dp[n][i]!=dp[0][0])
		{
			if (minx>abs(i-5000))
			{
				minx=abs(i-5000);
				ans=dp[n][i];
				rever=i;
			}
			else if (minx==abs(i-5000))
			{
				ans=min(dp[n][i],dp[n][rever]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

 

 

分类: DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.