多米诺骨牌解题报告【p1282】

2018-03-04 09:43:45


一个改动的背包问题,每个骨牌都有翻或不翻两种情况,因为如果当前的差值不一定能保证最终的差值最小,所以不能用贪心做,而状态转移数组里存的要是最小翻转次数。

:当要使用负的数组下标时,将数组平移到正的(最好 $\mathrm{define}$ 一个 $N$ ,更方便看)

总结:当有两个(或相似)状态时,且单个个数较多的,应该使用背包思想

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}
int abs(int x)
{
    if(x>=0)
        return x;
    return -x;
}
int f[1001][10001];//f[i][j]表示前i个差值为j-5000时的最小反转次数
int up[1001],down[1001];
int main()
{
    memset(f,0x3f,sizeof(f));
    f[0][5000]=0;
    int n,m,minn=9999999;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&up[i],&down[i]);
    for(int i=1;i<=n;i++)//做到第i个骨牌
        for(int j=-5000;j<=5000;j++)//j是实际差值
        {
            if(j-(up[i]-down[i])+5000>=0&&f[i-1][j-(up[i]-down[i])+5000]<0x3f3f3f3f)
                f[i][j+5000]=min(f[i][j+5000],f[i-1][j-up[i]+down[i]+5000]+1);
            if(j-(down[i]-up[i])+5000>=0&&f[i-1][j-(down[i]-up[i])+5000]<0x3f3f3f3f)
                f[i][j+5000]=min(f[i][j+5000],f[i-1][j-down[i]+up[i]+5000]);
        }
    for(int i=0;i<=5000;i++)
        if(f[n][5000-i]<0x3f3f3f3f||f[n][5000+i]<0x3f3f3f3f)
        {
            printf("%d\n",min(f[n][5000-i],f[n][5000+i]));
            return 0;
        }
    return 0;
}