解题报告 P1282 多米诺骨牌

题目内容

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行点数之差达到最小。

解题思路

设 f_{i,j} 表示前 i 个骨牌，上面一排的和为 j 时最小的反转次数，初始值赋无穷大，转移的时候考虑第 i 个转与不转的情况：

f_{i,j}=\min(f_{i,j},f_{i-1,j-a_i})

上面是不转的情况，很好理解，就是上面那枚骨牌的数字直接继承进来，然后不用反转。

f_{i,j}=\min(f_{i,j},f_{i-1,j-b_i}+1)

这是转的情况，就是继承下面那枚骨牌的数字，然后反转的次数要加一。

最后统计答案的时候，需要依据上下最小的差值来统计最小的反转次数，总的时间复杂度和空间复杂度为 O(n^2) 见代码：

#include <cstdio>

inline int min(int a,int b)
{
    return a<b?a:b;
}

inline int abs(int x)
{
    return x>=0?x:-x;
}

const int maxn=1005,inf=0x3f3f3f3f;
int a[maxn],b[maxn],n,sum,f[maxn][6*maxn];
//a记录上骨牌，b记录下骨牌，sum记录总的点数和

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",a+i,b+i);
        sum+=a[i]+b[i];
        for(int j=0;j<=6*n;j++)
            f[i][j]=inf;//先赋无限大
    }
    f[1][b[1]]=1,f[1][a[1]]=0;//这是初始状态，这里对顺序有要求，以避免第一枚骨牌上下相等导致的错误
    for(int i=2;i<=n;i++)
        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,ans=inf;//mind存储最小的上和下的差值
    for(int i=1;i<=sum;i++)
    {
        if(f[n][i]<inf)//如果当前状态可以达到
        {
            if(abs(i-(sum-i))<mind)//如果差值可以更小
                mind=abs(i-(sum-i)),ans=f[n][i];//更新最小差值和答案
            else if(abs(i-(sum-i))==mind)//否则如果差值相同
                ans=min(ans,f[n][i]);//也要统计最小的答案
        }
    }
    printf("%d\n",ans);
    return 0;
}