本文主要是介绍【万题详解】洛谷P1282 多米诺骨牌，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
链接——题目在这里！！！
多米诺骨牌由上下 22 个方块组成，每个方块中有 1∼6 个点。现有排成行的上方块中点数之和记为 S1，下方块中点数之和记为 S2，它们的差为 ∣∣S1−S2。如图S1=6+1+1+1=9，S2=1+5+3+2=11，|S1−S2∣=2。每个多米诺骨牌可以旋转 180°，使得上下两个方块互换位置。请你计算最少旋转多少次才能使多米诺骨牌上下 2行点数之差达到最小。
对于图中的例子，只要将最后一个多米诺骨牌旋转 180°，即可使上下 2行点数之差为 0。
输入格式
输入文件的第一行是一个正整数 n(1≤n≤1000)，表示多米诺骨牌数。接下来的 n 行表示 n 个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数 a 和 b，且 1≤a,b≤6。
输出格式
输出文件仅一行，包含一个整数。表示求得的最小旋转次数。
输入输出样例
输入 #1
4
6 1
1 5
1 3
1 2
输出 #1
1
解题思路
题目要求的是最小差值情况下的最小交换次数，那么我们把其中一个计入状态里。记交换次数好像不太好做（我没试过），所以我们要记的是差值。
但是差值是一个绝对值，好像也不是很好表示，所以我们再来转化一下。观察到每次交换只是把上下两个数交换，故前i个骨牌上下两行数的总和是不变的，所以我们只需记录其中一行数字的和就可以知道差值了。这样状态就好表示了。
f[i][j]表示前i个数字，第一行的数字和是j时，最小的交换次数。初始值所有f[i][j]都是无穷大，f[1][a[1]]=0，f[1][b[1]]=1。（a[]和b[]分别表示第一行和第二行的数字）
转移时，枚举每一个可能的和，共有6*n个，考虑当前一个交不交换即可：
if (j-a[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-a[i]]); //当前不交换
if (j-b[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-b[i]]+1); //当前交换
求答案时再枚举一下前n个骨牌第一行的和就好。
这样时间、空间复杂度均为O(n*n*6)。
我们发现，每一组骨牌对答案的贡献都是独立的，所以可以单独计算。
设计状态为f[i][j],表示处理到第i个骨牌，所有上面的数减去所有下面的数的值为j的最小旋转次数。因为每一组的差值不超过5，最多有1000组骨牌，所以j的范围是-5000~5000。处理时将j都加上5000，来处理负数下标~~【本来没有考虑到这个竟然也过了...果然玄学】~~
状态转移方程为f[i][j]=min(f[i-1][j-(a[i]-b[i])],f[i-1][j-(b[i]-a[i])]+1);
即如果不旋转，第i组骨牌的结果是a[i]-b[i]，所以从f[i-1][j-(a[i]-b[i])]转移过来，答案不加，如果旋转，第i组骨牌的结果是b[i]-a[i]，所以从f[i-1][j-(b[i]-a[i])]转移过来，答案+1。
剩下的就是统计答案了，按绝对值从小到大找，找到第一个有解的值就是答案，即差值最小时的答案，如果正负同时成立，就取最小值
AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005,INF=0x3f3f3f3f;
int a[maxn], b[maxn];
int dp[maxn][10 * maxn];
int n;
int N = maxn * 5;
int main(){cin >> n;for(int i = 1; i <= n; i++){cin >> a[i] >> b[i];}memset(dp,INF, sizeof(dp));dp[0][N] = 0;for(int i = 1; i <= n; i++){for(int j = -N; j <= N; j++){int dis = a[i] - b[i];dp[i][j + N] = min(dp[i - 1][j - dis + N], dp[i - 1][j + dis + N] + 1); }}int minn;for(int i = 0; i <= N; i++){minn = min(dp[n][i + N], dp[n][-i + N]);if(minn != INF){cout << minn << endl;break;}}return 0;
}这篇关于【万题详解】洛谷P1282 多米诺骨牌的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
