Luogu-P1282-多米诺骨牌

Posted on Edited on Word count in article: 796

第一篇题解，纪念！

题目 P1282 多米诺骨牌

题目描述

多米诺骨牌由上下 $2$ 个方块组成，每个方块中有 $1\sim6$ 个点。现有排成行的上方块中点数之和记为 $S_1$，下方块中点数之和记为 $S_2$，它们的差为 $\left|S_1-S_2\right|$。如图，$S1=6+1+1+1=9$，$S2=1+5+3+2=11$，$\left|S_1-S_2\right|=2$。每个多米诺骨牌可以旋转 $180°$，使得上下两个方块互换位置。请你计算最少旋转多少次才能使多米诺骨牌上下 $2$ 行点数之差达到最小。

对于图中的例子，只要将最后一个多米诺骨牌旋转 $180°$，即可使上下 $2$ 行点数之差为 $0$。

输入格式

输入文件的第一行是一个正整数 $n(1\leq n\leq 1000)$，表示多米诺骨牌数。接下来的 $n$ 行表示 $n$ 个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数 $a$ 和 $b$，且 $1\leq a,b\leq 6$。

输出格式

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

思路：dp

dp表

使用一维的dp，$dp[i]$ 表示使上层总和为 $i$ 的最小翻转次数（实际上，选取上层和下层等效）。

依次输入每个牌的上层 $t_1$ 和下层 $t_2$，输入的同时进行状态转移，并记录上下牌的总和 $sum$。

状态

  • 初状态：所有值均为 $+\infty$。

  • 状态转移方程：

    1
    2
    3
    dp[i + t1] = min(dp[i + t1], dp[i]);
    dp[i + t2] = min(dp[i + t2], dp[i] + 1); // Reverse
    dp[i] = inf;

  • 末状态：为了使差最小，应该从中间 $mid = \cfrac{sum}2$ 向外遍历，同时需要根据 $sum$ 的奇偶讨论

    | | 起点 | 循环变量范围 | 本次遍历下标 |
    |–|————– -|————-|———————|
    |奇| $mid, mid+1$ | $[0, mid]$ | $mid-i, mid+1-i$ |
    |偶| $mid$ | $[0, mid]$ | $mid-i, mid+i$ |

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// template v6
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

inline void maxset(int &t, int other) {
    t = max(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = 1010;

int sum;

int dp[N * 12]; // top numbers

int main() {
    memset(dp, 0x7f, sizeof dp);
    dp[0] = 0;
    int n;
    cin >> n;
    int t1, t2;
    for(int i = 0; i < n; i++) {
        cin >> t1 >> t2;
        sum += t1 + t2;
        for(int i = sum; i >= 0; i--) {
            if(dp[i] != inf) {
                minset(dp[i + t1], dp[i]);
                minset(dp[i + t2], dp[i] + 1);
                dp[i] = inf;
            }
        }
    }
    const int mid = sum / 2;
    int ans = inf;

    if(sum % 2) {
        // odd
        for(int i = 0; i <= mid; i++) {
            minset(ans, min(dp[mid - i], dp[mid + 1 + i]));
            if(ans != inf){
                cout << ans << endl;
                break;
            }
        }
    } else {
        // even
        for(int i = 0; i <= mid; i++) {
            minset(ans, min(dp[mid - i], dp[mid + i]));
            if(ans != inf){
                cout << ans << endl;
                break;
            }
        }
    }
    return 0;
}