多米诺骨牌

发表于 更新于 分类于

Problem’s Website

  • 多米诺骨牌

    Solution

  • 这道题可以看做一个线性dp，也可以看做背包问题，根据题意，我们发现一张牌转两次及以上是没有意义的，那么我们可以设f[i][j]表示到第i个数上下点数之差为j的旋转次数，对于i和i+1，状态转移方程为

    1
    f[i][j] = min(f[i - 1][j - a[i]),f[i - 1][j + a[i]] + 1);

    a[i]为上下一张牌上下点数之差，为了防止数组下标出现负数，我们把每个j加上一个num，最后通过枚举找到差值最小的f[i][j],记录最小转动次数。

    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
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    #define num 5000
    using namespace std;
    int sc() {
        int xx = 0, ff = 1; char cch = gc;
        while(cch < '0' || cch > '9') {
            if(cch == '-') ff = -1; cch = gc;
        }
        while(cch >= '0' && cch <= '9') {
            xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
        }
        return xx * ff;
    }
    int n, ans;
    int a[1010], f[1010][10010];
    int main() {
        n = sc();
        for(int i = 1; i <= n; i++) {
            int x = sc(), y = sc();
            a[i] = x - y;
        }
        memset(f, 0x7f, sizeof(f));
        f[0][0 + num] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = -5000 ; j <= 5000; j++) {
                f[i][j + num] = min(f[i - 1][j + num - a[i]], f[i - 1][j + num + a[i]] + 1);
            }
        }
        for(int i = 0; i <= 5000; i++) {
            ans = min(f[n][i + num], f[n][num - i]);
            if(ans <= 1000) {
                printf("%d\n", ans);
                return 0;
            }
        }
        return 0;
    }

rp++