【SSL】1632骨牌游戏(多米诺骨牌)

本文主要是介绍【SSL】1632骨牌游戏(多米诺骨牌)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【SSL】1632骨牌游戏(多米诺骨牌)

Time Limit:1000MS

Memory Limit:65536K

Description

在这里插入图片描述

Input

输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。

Output

输出文件仅一行，包含一个整数。表示求得的最小旋转次数。

Sample Input

Sample Output

思路

用f[i][j]表示前i张骨牌构成差值j要翻动的最小骨牌数。我们可以列出如下方程：
f[i][j] = min(f[i-1][j-(a[i]-b[i])], f[i-1][j-(b[i]-a[i])]+ 1}
由于第一种选择不翻动第I张骨牌，所以最小翻动次数在原基础上不变。
而第二种选择要翻动骨牌i，所以最小翻动次数要加1。
边界：f[0, 0] =0
初始化：将整个F数组的值都附成一个足够大的数MAX，如果用前i张骨牌不可构成差值j，最后f[i][j]的值一定为MAX。要求出最小差值和最小翻动次数，只要从f[n][j]中选出一个不为max，且绝对值最小的j，选出的j对应的min(f[n][j],f[n][-j])的值即为问题的解。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[1010],b[1010],f[1010][12010],maxn=1684300900;
void input()
{int i;memset(f,100,sizeof(f));//赋最大值scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);return;
}
void DP()
{int i,j;f[0][6000]=0;for(i=1;i<=n;i++){for(j=-6000;j<=6000;j++){f[i][j+6000]=min(f[i-1][j-(a[i]-b[i])+6000],f[i-1][j-(b[i]-a[i])+6000]+1);//状态转移方程}}return;
}
void output()
{int i;for(i=0;i<=6000;i++)//找最小差if (f[n][i+6000]<maxn||f[n][6000-i]<maxn){printf("%d",min(f[n][i+6000],f[n][6000-i]));return;}return;
}
int main()
{input();DP();output();return 0;
}