Luogu P1282 多米诺骨牌

YorkWu

May 8, 2019

1210 views

No comments

888 words

OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P1282 "题目链接") 总结一下：这种题用背包。。。（蒟蒻的我看不出来qwq）

* * *

我们先把骨牌翻转，调整至点数大的在上面 这样，我们就能保证上方的点数一定比下方大，并且保证每翻转一 次，都能使上下的点数之差变小，而变小的点数，就是上下点数之差乘以2。 把改变的点数看成物品的体积，初始上下方的点数之差看做背包体积，不难看出背包问题的模型。 那么物品的重量是什么呢？ 因为我们一开始就把点数大的放在了上面，而每放一次，翻转次数就+1。考虑：要是我后来后悔了，我发现不翻这个骨牌更好怎么办？那我会把它翻回来，那么相当于没有翻这个骨牌。 因此，一开始翻过的骨牌重量就是-1，未翻过的骨牌重量就是1（重量等价于翻转次数） 当然，上下相同的骨牌就是体积为0，重量为0的物品，因为他们无论怎么翻，都不会对上下点数差造成影响。 至此，背包的模型就出来了。这个问题被简化成：有n个物品，给出每个物品的体积v\[i\],他们的重量是1或-1。背包的重量为base，体积为tot，现在请把这n个物品放到背包里去，总体积不能超过tot，体积最大的情况下使得物品重量之和最小。 其中，dp\[i\]\[j\]表示前i件物品能装到体积为j的最小重量 vs\[i\]\[j\]表示前i件物品能否装到j体积
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,m,c;
    struct node{
        int a,b;
    }a[1009];
    int f[1009][5009],v[1009],w[1009];
    bool vis[1009][5009];
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].a>>a[i].b;
            if(a[i].a<a[i].b){
                swap(a[i].a,a[i].b);
                w[i]=-1;
                v[i]=a[i].a-a[i].b;
                m+=v[i];
                v[i]*=2;
                c++;
            }
            else{
                w[i]=1;
                v[i]=a[i].a-a[i].b;
                m+=v[i];
                v[i]*=2;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[i][j]=f[i-1][j];
                vis[i][j]=vis[i-1][j];
                if(vis[i-1][j-v[i]]||j-v[i]==0){
                    if(!vis[i][j]){
                        f[i][j]=f[i-1][j-v[i]]+w[i];
                        vis[i][j]=1;
                    }
                    else{
                        f[i][j]=min(f[i][j],f[i-1][j-v[i]]+w[i]);
                    }
                }
            }
        }
        for(int i=m;i>=0;i--){
            if(vis[n][i]){
                cout<<f[n][i]+c;
                return 0;
            }
        }
        return 0;
    }
```

Last modification：March 14, 2020