多米诺骨牌

首先分析状态表示：
分析：每个骨牌可以旋转一次，找最小的旋转次数使得上面减下面的绝对值最小
每个骨牌可以旋转一次可以看出是01背包


如果我们直接把状态表示定为前i个物品在差值的绝对值为j时最小的旋转次数，这个差值就会有很多种情况，很难枚举


（因为太菜只能）
再来分析：根据题意可以分析得出，无论怎样旋转，总点数是不变的，那我就可以根据 ”总和是不变的“ 和 “上面那一行的和” 来表示下一行的和，这样就可以将情况减少很多，变为了6*n种情况

那么最终的状态表示就为前i个物品上行的和为j时的最小旋转次数

下面根据代码理解：

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 1010;
int n;
int s;
int f[N][6 * N];
int a[N];
int b[N];

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++) 
	{
		cin >> a[i] >> b[i];	
		s += a[i] + b[i];	//计算所有多米诺骨牌的和	
	}
	
	memset(f, inf, sizeof f);	//因为要计算最小值，所有用inf初始化
	f[1][a[1]] = 0; // 第一个为上行没有交换，值为0
	f[1][b[1]] = 1; // 交换了，值为1
	
	for(int i = 2; i <= n; i ++)
		for(int j = 0; j <= 6 * n; j ++)// 枚举6*n种情况
		{
			if(j >= a[i]) //不交换
			f[i][j] = min(f[i][j], f[i - 1][j - a[i]]);
			if(j >= b[i]) //交换
			f[i][j] = min(f[i][j], f[i - 1][j - b[i]] + 1);
		}
	
	int minn = inf, ans = inf;
	for(int i = 0; i <= s; i ++) // 枚举所有情况
	{
		if(f[n][i] != inf) //保证有意义
		{
			if(minn > abs(i - (s - i))) 
			{
				minn = abs(i - (s - i));
				ans = f[n][i];
			}
			else if(minn == abs(i - (s - i)))
			{
				ans = min(ans, f[n][i]);
			}
		}
	}
	cout << ans << endl;
}

。