蓝桥杯备考：多米诺骨牌

这道题要求上下方格子和之差要最小，其实就是算每个上下格子的差求和的最小值

这道题其实是动态规划01背包问题

我们直接按步骤做吧

step1:定义状态表示f[i][j]表示从1到i个编号的差值里选出刚好j个数的最小操作次数

step2:推导状态转移方程

如图这就是我们的状态转移方程，由于它既是需要上面的左边区域也是需要上面的右边区域，so不能进行空间优化了

step3：初始化

把f[0][0]初始化为0，其他的全初始化为无穷大

step4:结果怎么看，

我们发现，最大的情况就是上面全部都是6，下面全是1，这时候我们的差值的和就是5000

我们设x遍历1到5000，比较x和-x，如果有答案，取最小的数

但是有一点就是，我们的和是可能是负数的，那时候我们怎么存？我们可以把dp表所有格子整体右移动m单位

下面是我们实现的代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
const int M = 1e4+10;
const int INF = 0x3f3f3f3f;
int n;
int f[N][M];
int a[N];
int main()
{cin >> n;for(int i = 1;i<=n;i++){int x,y;cin >> x >> y;a[i] = x-y;}memset(f,0x3f,sizeof(f));int m = 5000;f[0][0+m] = 0;for(int i = 1;i<=n;i++){for(int j = -m;j<=m;j++){f[i][j+m] = min(f[i-1][j-a[i]+m],f[i-1][j+a[i]+m]+1);}}int ret = INF;for(int j = 0;j<=m;j++){ret = min(f[n][j+m],f[n][-j+m]);if(ret!=INF) break;}cout << ret;return 0;
}