问题描述：
有一种多米诺骨牌是平面的，其正面被分成上、下两个部分，每一部分的表面或者为空，或者被标上1至6个点。现在有一行多米诺骨牌排列在桌面上，如下图：
顶行（上行）骨牌的点数之和为6+1+1+1=9；底行（下行）骨牌的点数之和为1+5+3+2=11。顶行和底行的差值是2，这个差值是上、下两行点数之和的差的绝对值。每个多米诺骨牌都可以上下翻转倒置交换，即上部变为下部，下部变为上部。
现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需要翻转最后一个骨牌，就可以使得顶行和底行的差值为0。所以这个例子的答案为1。
__输入格式__：
第1行是一个整数n（1<=n<=1000），表示有n个多米诺骨牌。
接下来共有n行，每行包含两个整数a,b（0<=a,b<=6），之间用一个空格隔开，第i+1行的a,b分别表示第i个多米诺骨牌的上部和下部的点数（0表示空）。
__输出格式__：
一行只有一个整数，表示最少需要的翻转次数，从而使得顶行和底行的差值最小。
__输入样例__：
4
6 1
1 5
1 3
1 2
__输出样例__：
1
解决思路1：
背包问题的变型
以骨牌顶行的和为背包，其最大容量为sum/2，(sum为所有骨牌顶行和底行之和)，每个骨牌都有两种入包的选择，顶行的数或底行的数，产生的翻转分别为0和1，选择入包的方法，使其和最接近sum/2，而且其翻转次数最少。
DP[i][j]=min(DP[i-1][j-顶行的数],DP[i-1][j-底行的数],DP[i][j])
DP数组的初值都赋为最大值，因为每个骨牌在选择时，必须要求前面的骨牌已选择，类似于背包的“恰好装满”。
代码示例（c++）:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
for(int n;cin>>n;)
{
int i,j;
vector<int> first(n+1),second(n+1);
int sum=0;
for(i=1;i<=n;i++)
{
cin>>first[i]>>second[i];
sum+=first[i]+second[i];
}
sum/=2;
vector<vector<int> > DP(n+1,vector<int>(sum+1,10000));
DP[0][0]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=sum;j++)
{
if(j>=first[i] && DP[i-1][j-first[i]]<DP[i][j]) DP[i][j]=DP[i-1][j-first[i]];
if(j>=second[i] && DP[i-1][j-second[i]]+1<DP[i][j]) DP[i][j]=DP[i-1][j-second[i]]+1;
}
}
for(j=sum;j>=1;j--)
if(DP[n][j]!=10000)
{
cout<<DP[n][j]<<endl;
break;
}
}
}
|
解决思路2
骨牌顶行的点数之和，与骨牌底行点数之和之差一开始是确定的，6+1+1+1-（1+5+3+2）=-2，每一个骨牌的翻转对差的影响分别为-10，8,4,2，这样枚举所有出现的差的情况，每种差都选择翻转次数最小达到的情况。
这种思路的优点在于压缩了状态，使影响结果的状态由两种变为一种。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| 代码示例（c++）：
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
for(int n;cin>>n;)
{
vector<int> data(n);
int i,j;
int first,second;
int sum=0,dif=0;
for(i=0;i<n;i++)
{
cin>>first>>second;
data[i]=(second-first) * 2;
dif+=first-second;
sum+=(first>=second?first-second:second-first);
}
if(dif==0)
{
cout<<0<<endl;
continue;
}
vector<int> DP1(sum*2+1,10000),DP2(sum*2+1,10000);
for(j=0;j<=sum*2;j++)
DP1[j]=10000;
DP1[dif+sum]=DP2[dif+sum]=0;
for(i=0;i<n;i++)
{
for(j=sum*2;j>=0;j--)
if(DP1[j]!=10000)
if(DP2[j+data[i]]>DP1[j]+1) DP2[j+data[i]]=DP1[j]+1;
DP1=DP2;
}
int min=10000,turn=10;
for(j=0;j<=sum*2;j++)
if(DP1[j]!=10000)
if(abs(j-sum)<min)
{
min=abs(j-sum);
turn=DP1[j];
}
else if(abs(j-sum)==min && turn<DP1[j])
turn=DP1[j];
cout<<turn<<endl;
}
}
|
解决思路3：
以最少的翻转次数，使得顶行和底行之间的差值最小
一个骨牌对翻转策略造成影响的是上下两数之差，把骨牌的放置状态由8个数字变为4个：5 -4 -2 -1，翻转时只需取该位数字的相反数就行了。
抽象为一个数学模型：给定一组整数，每个数可以翻转成其相反数，以最少的翻转次数，使这个序列的和的绝对值最小。
以树来表示，每个数都有两种出现方式：或正或负，这样就构成了一棵完全二叉树。设所有数都以正的情况出现的和为sum，则这个数列的和的范围为-sum到sum之间，为了使数组的下标正好对应其每一种和的状况，让每个数列和加上sum。
这种思路下，好像有更优的解法，没有理解，欢迎交流。