多米诺骨牌

洛谷-P1282-多米诺骨牌

分析

把求解转化为判定。

实现

#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 1010, M = 12010, offset = 6000;
int n, up[N], down[N];
int f[N][M];
// f[i][j + offset] 记录当前 i 张骨牌的上下点数之差为 j 时最少的旋转次数

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> up[i] >> down[i];

    memset(f, 0x3f, sizeof(f));
    f[0][0 + offset] = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = -6000; j <= 6000; ++ j) {
            int a = f[i - 1][j + offset - up[i] + down[i]],
                b = f[i - 1][j + offset + up[i] - down[i]] + 1;
            f[i][j + offset] = min(a, b);
        }
    }

    for (int i = 0; i <= 6000; ++ i) {
        int res = min(f[n][-i + offset], f[n][i + offset]);
        if (res != inf) {
            cout << res << endl;
            break;
        }
    }
    return 0;
}