题解 P1282 【多米诺骨牌】

· · 题解

DP.

题目要求的是最小差值情况下的最小交换次数，那么我们把其中一个计入状态里。记交换次数好像不太好做（我没试过），所以我们要记的是差值。

但是差值是一个绝对值，好像也不是很好表示，所以我们再来转化一下。观察到每次交换只是把上下两个数交换，故前i个骨牌上下两行数的总和是不变的，所以我们只需记录其中一行数字的和就可以知道差值了。这样状态就好表示了。

f[i][j]表示前i个数字，第一行的数字和是j时，最小的交换次数。初始值所有f[i][j]都是无穷大，f[1][a[1]]=0，f[1][b[1]]=1。（a[]和b[]分别表示第一行和第二行的数字）

转移时，枚举每一个可能的和，共有6*n个，考虑当前一个交不交换即可：

if (j-a[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-a[i]]);  //当前不交换
if (j-b[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-b[i]]+1);  //当前交换

求答案时再枚举一下前n个骨牌第一行的和就好。

这样时间、空间复杂度均为O(n*n*6)。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1000;
const int INF = 1e9;
int a[N+10], b[N+10], f[N+10][6*N+10];

int main()
{
    int n;
    scanf("%d", &n);
    int s = 0;
    for (int i = 1; i <= n; i ++){
        scanf("%d%d", &a[i], &b[i]);
        s += a[i] + b[i];
    }
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= 6*n; j ++) f[i][j] = INF;
    f[1][a[1]] = 0; f[1][b[1]] = 1;
    for (int i = 2; i <= n; i ++)   //DP，解释如上
        for (int j = 0; j <= 6*n; j ++){
            if (j-a[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-a[i]]);
            if (j-b[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-b[i]]+1);
        }
    int minD = INF, minT = INF;  //minD是最小差值，minT是最小交换次数
    for (int i = 0; i <= s; i ++)
        if (f[n][i] != INF){
            if (abs(i-(s-i)) < minD){
                minD = abs(i-(s-i)); minT = f[n][i];
            }
            else if (abs(i-(s-i)) == minD) minT = min(minT, f[n][i]);
        }
    printf("%d", minT);
    return 0;
}