题意

多米诺骨牌有上下$2$个方块组成，每个方块中有$1$~$6$个点。现有排成行的上方块中点数之和记为$S_1$，下方块中点数之和记为$S_2$，它们的差为$|S_1-S_2|$。 例如在图中，$S_1$=$6$+$1$+$1$+$1$=$9$，$S_2$=$1$+$5$+$3$+$2$=$11$，$|S_1-S_2|$=$2$。每个多米诺骨牌可以旋转$180$°，使得上下两个方块互换位置。
编程用最少的旋转次数使多米诺骨牌上下$2$行点数之差达到最小。

解题思路

该题为变形的$0$-$1$背包，如果能做到很好的转化解决起来不是很难。 这里将$gap$值做为背包容量（注意这里$gap$有可能为负值， 可以给其加上一个定值，将负值变为正值），用反转一次骨牌对$gap$的影响值。 $change[i]$做为物品往背包里放，同样这个影响值，既价值同样有存在负值的情况，于是按$0$-$1$背包的思想可得到转移方程：$dp[i][j] = \min(dp[i - 1][j], dp[i - 1][j - change[i]] + 1)$：其中$i$为骨牌号，$j$为$gap$值。 这里需要注意动规数组存放的值的意思，这一点必须弄清，其实该数组中存放的值为：要使差值改变$gap$最少的反转次数（这里要好好理解）。 正是由于动规数组里存放着这样的值，因此在最后只要找到一个这样的值就行：与$fix + gap$最接近的$i$，同时$dp[fix + gap - i]$或$dp[fix + gap + i]$有值即可，注意如果对称着都存在值，取出两者中最小的即可。

标程

#include <iostream>
#include <algorithm>
using namespace std;
const int nmax = 19870711;
const int fix = 20000;

int n;
int dp[35000];
int up, down, gap;
int change[1010];
int nright, nletf;

int main()
{
    int i, j;
    while(cin>>n)
    {
        //初始化
        gap = 0;
        nright = nletf = fix;
        for(i=fix-n*12; i<=fix+n*12; ++i)
            dp[i] = nmax;
        dp[fix] = 0; 

        //读入数据
        for(i=1; i<=n; ++i)
        {
            cin>>up>>down;
            change[i] = (up - down) * 2;
            gap += (up - down);
        }

        //0-1背包处理
        for(i=1; i<=n; ++i)
        {
            if(change[i] > 0)
                for(j=nright+change[i]; j>=nletf+change[i]; --j)
                    dp[j] = min(dp[j], dp[j-change[i]]+1);
            if(change[i] < 0)
                for(j=nletf+change[i]; j<=nright+change[i]; ++j)
                    dp[j] = min(dp[j], dp[j-change[i]]+1);
            nright = max(nright, nright+change[i]);
            nletf = min(nletf, nletf+change[i]);
        }

        //找最优解
        int ans;
        for(i=0; i<=n*12; ++i)
        {
            if(dp[fix+gap-i]<nmax || dp[fix+gap+i]<nmax)
            {
                ans = min(dp[fix+gap-i], dp[fix+gap+i]);
                break;        
            }
        } 
        cout<<ans<<endl;
    }
    return 0;
}