洛谷 P1282 多米诺骨牌

题目描述

多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的

上方块中点数之和记为S1，下方块中点数之和记为S2，它们的差为|S1-S2|。例如在图8-1中，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。

输出格式：

输出文件仅一行，包含一个整数。表示求得的最小旋转次数。

---

f[i][j]表示前i个多米诺骨牌上下差值为j的最小次数，//因为差值可能为负数，所以都加上了5001；

枚举所有的骨牌和可能达到的差值，则显然有：

f[i][j] = min(f[i - 1][j - (up[i] - down[i])],f[i - 1][j - (down[i] - up[i])] + 1); // 不翻或翻转；

最后从0枚举所有的情况就A掉了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 100;
const int MAXM = 5e3 + 1;

inline int read() {
    int x = 0, ff = 1; char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') ff = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * ff;
}

inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int n,up[MAXN],down[MAXN],f[1005][10005];

int main() {
    memset(f, 0x3f, sizeof(f));
    n = read();
    for(int i = 1; i <= n; ++i) {
        up[i] = read();
        down[i] = read();
    }
    f[1][up[1] - down[1] + MAXM] = 0;
    f[1][down[1] - up[1] + MAXM] = 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = -5000; j <= 5000; ++j) {
            f[i][j + MAXM] = min(f[i - 1][j - up[i] + down[i] + MAXM],f[i - 1][j + up[i] - down[i] + MAXM] + 1);
        }
    }
    for(int i = 0; i <= 5000; ++i) {
        if(f[n][i + MAXM] <= 1000 || f[n][-i + MAXM] <= 1000) {
            write(min(f[n][i + MAXM], f[n][-i + MAXM]));
            return 0;
        }
    }
    return 0;
}