Luogu-1282-多米诺骨牌

多米诺骨牌有上下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。

题目链接

Luogu-1282-多米诺骨牌

输入输出格式

输入格式

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

输出格式

输出一行,为世界末日的日期,每个数字之间用一个空格隔开。

输入输出样例

输入样例1:

4
6 1
1 5
1 3
1 2

输出样例1:

1

题解

很显然是个 dp 题目,显然蓝题 dp 我不会写,自己瞎定义了一个 $dp[i][j]$ ,发现没法进行状态转移,看了题解说我定义的方程太麻烦很难写????喵喵喵???然后看了题解的 $dp$ 的定义方法,写了下去。

一开始我定义的 $dp[i][j]$ 是前 $i$ 个牌,翻转 $j$ 次的上下差值。我不会推状态转移方程,后期刷多了再推把。

题解的定义为 $dp[i][j]$ 代表前 $i$ 个牌组成和为 $j$ 的旋转次数。对于这种定义,我们可以暴力枚举,前 $i$ 能组成的所有和,即

$dp[i][j] = min(dp[i][j],dp[i-1][j - a[i]]) // 不翻转$
$dp[i][j] = min(dp[i][j],dp[i-1][j - b[i]] + 1) // 翻转$

对于 $j$ 而言,前 $i$ 个骨牌所能组成的最大总和为 $6 * n$ ,所以时间复杂度为 $O(6*n^2)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e3 + 5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int dp[1005][6005];
int a[MAXN],b[MAXN];
int main() {
    ios::sync_with_stdio(false);
    int n,sum = 0;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i] >> b[i];
        sum += a[i] + b[i];
    }
    memset(dp,INF,sizeof(dp));//最初所有能组成的点数之和的翻转次数都是INF
    dp[1][a[1]] = 0;dp[1][b[1]] = 1; //第一块骨牌的上为0,下为1
    
    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= 6*n;j++){
            if(j >= a[i])
                dp[i][j] = min(dp[i][j],dp[i-1][j - a[i]]);
            if(j >= b[i])
                dp[i][j] = min(dp[i][j],dp[i-1][j - b[i]] + 1);
        }
    }

    int cut = INF,cnt = INF;
    for(int i = 1;i <= sum;i++){
        if(dp[n][i] != INF){ //如果这n个牌能到达和为i
            if(cut > abs(i - (sum - i))){
                cut = abs(i - (sum - i));
                cnt = dp[n][i];
            } else if(cut == abs(i - (sum - i))){
                cnt = min(cnt,dp[n][i]);
            }
        }
    }
    cout << cnt << endl;
    return 0;
}