洛谷 P1282 多米诺骨牌

url: https://www.luogu.com.cn/problem/P1282

tag:
动态规划，枚举，背包DP

思路：
用 f[i][j] 表示用前i块多米诺骨牌形成的差值为j时旋转次数。因为差值的范围是-5000-5000，所以数组加一个5000的偏移量。状态转移方程为 f[i][j + p] = min(f[i - 1][j - (a[i] - b[i]) + p], f[i - 1][j - (b[i] - a[i]) + p] + 1); 。 j - (a[i] - b[i]) + p 表示未加上第i块多米诺骨牌时的差值。上下旋转时，当前的差值会反过来，同时次数也要加一。最后求答案值，求绝对值从小到大第一个合法的值就是答案（正负都合法的话取一个最小值），表示差值最小时的旋转次数。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010, p = 5000;
int f[N][N * 6 * 2];
int a[N], b[N];
int n;
int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    f[1][0 + p + a[1] - b[1]] = 0, f[1][0 + p + b[1] - a[1]] = 1;
    if (a[1] == b[1]) f[1][p] = 0;
    for (int i = 2; i <= n; i ++)
    {
        for (int j = -5000; j <= 5000; j ++)
        {
            f[i][j + p] = min(f[i - 1][j - (a[i] - b[i]) + p], f[i - 1][j - (b[i] - a[i]) + p] + 1);
        }
    }
    int res = 0x3f3f3f3f;
    for (int i = 0; i <= 5000; i ++)
    {
        if (f[n][i + p] <= 1000 || f[n][-i + p] <= 1000)
        {
            res = min(f[n][i + p], f[n][-i + p]);
            break;
        }
    }
    cout << res << endl;
    return 0;
}