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

对于图中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。

输入输出格式
输入格式：
输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。

输出格式：
输出文件仅一行，包含一个整数。表示求得的最小旋转次数。

输入输出样例
输入样例：
4
6 1
1 5
1 3
1 2
输出样例：
1

由于这题有负数，所以我们可以取一个较大的下标作为数组的基准值（也就是设x为0）
然后通过DP求解

先将所有骨牌的初始状态先求出来

cin>>n;
    int x,y,z;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        a[i]=x-y;//这里的a[i]就代表了多米诺骨牌的上下点数之差，因为翻转以后点数差会取负所以直接存这个差值就可以
        z+=a[i];//z求出来的即是初始的上下点数总差
    }

然后在这里我随便选了个20000作为基准数，只要保证在接下来的计算过程中下标不会变负即可
除了初始状态标记翻转次数为0以外其他值就用一个很大的数来表示无法达到

for(int i=0;i<40000;i++)s[i]=INF;
s[20000-z]=0;

接下来就是主要的DP过程了，而点数之差的正负也又要进入我们的考虑范围，相信大家在学01背包的时候都思考过下面这个循环：

for(int i=1;i<=n;i++){
    for(int j=m;j>=v[i];j--){//m为背包的容量
        s[j]=max(s[j],s[j-v[i]]+w[i]);//v[i]:物品的体积，w[i]:物品的价值
    }
}

当时一直不是很明白为什么j是从大到小循环，后来才知道如果是正着循环的话，当前循环中更新的s[j]会在接下来成为新的s[j’-v[i]],这就影响到了s[j’]的结果，而反过来循环就不会，还不懂的童鞋可以自己去试着推一下。
同理我们再来看这道题也是如此,略有不同的是多米诺骨牌翻转后对于整体来讲是改变了两倍的a[i]：

s[j]=min(s[j],s[j-2*a[i]]+1);

当a[i]为正的情况下，j-2*a[i]<j，我们要保证更新完s[j]后不会影响到本次循环其他的更新，因此我们从后往前循环，这里我的10000和30000都是随意取的，只是保证不越界。

if(a[i]<0){
    for(int j=10000;j<=30000;j++){
        s[j]=min(s[j],s[j-2*a[i]]+1);
    }
}

a[i]为负则反之

else if(a[i]>0){
    for(int j=30000;j>=10000;j--){
        s[j]=min(s[j],s[j-2*a[i]]+1);
    }
}

最后我们以之前选的基准数为起点，同时往前后推，若是遇见可以翻转到的点数，就输出次数并结束循环

for(int i=0;i<=6000;i++){
    if(s[20000+i]<1000||s[20000-i]<1000){
        cout<<min(s[20000+i],s[20000-i]);//这里还需判断一下正负点数哪种次数比较小
        return 0;
    }
}

完整代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string.h>
#include <string>
#include <queue>
#include <stack>
#include <map>
using namespace std;
#define FI first
#define SE second
#define PB push_back
#define PII pair<int,int>
#define LL long long int
#define DEBUG cout<<1<<endl;
const int INF=1e8;
int a[10101],s[40011];
int n;
int main()
{
    for(int i=0;i<40000;i++)s[i]=INF;
    cin>>n;
    int x,y,z;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        a[i]=x-y;
        z+=a[i];
    }
    s[20000-z]=0;
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            for(int j=10000;j<=30000;j++){
                s[j]=min(s[j],s[j-2*a[i]]+1);
            }
        }
        else if(a[i]>0){
            for(int j=30000;j>=10000;j--){
                s[j]=min(s[j],s[j-2*a[i]]+1);
            }
        }
    }
    for(int i=0;i<=6000;i++){
        if(s[20000+i]<1000||s[20000-i]<1000){
            cout<<min(s[20000+i],s[20000-i]);
            return 0;
        }
    }
    return 0;
}