题解 P3052 【[USACO12MAR]Cows in a Skyscraper G】

· · 题解

注:本题解物品已经其他的下标都是从0开始。

建议看本题解前先学习状态压缩dp,不然你很可能看不懂,或跳过本题解。

首先看到数据范围,n<=18,就要想到3个算法。

①模拟退火②dfs③状态压缩dp。

太巧了,这道题3个方法都可以。但我不推荐算法①,具有随机性。

我要讲的是算法②----------状态压缩dp。

因为n很小,所以直接设f[i]为所以物品选不选的最小答案。(二进制位从左数第j位中0为不选第j件物品,1为选。)例如n=3,i=(101)_2时,就表示0号物品和2号物品选,n=5,i=(11001)_2时,就表示第0,3,4物品选。

转移:我们如果塞得下这个物品,就直接转移就行了。如果塞不下,就要重新开一个组。所以就要+1。

因为我们要检查塞不塞得下,所以必须设一个另外的数组表示还剩余多少空间。这里就叫做size。

所以我们可以得到以下方程。其实b只是为了写得清楚方便而暂时把值存在b里。实际代码根本不需要。

b=\begin{cases}f[i]\kern{20pt}(a[j]<=size[i])\\f[i]+1\kern{3pt}(a[j]>\kern{8pt}size[i])\\\end{cases}

注:f数组的值要对原先的值取min(具体可见代码)。这样才能保证最小。

注意看清f数组中的中括号[和或运算|,其中f数组的中括号已标红。

f\color{red}{[}\color{black}i|(1<<j)\color{red}{]}\color{black}=min(f\color{red}{[}\color{black}i|(1<<j)\color{red}{]}\color{black},b)

当f数组更新了(b要小一些),就表示这种方法得到的数更小。所以我们也就要把size数组更新。

为了方便我就继续设一个b。

b=\begin{cases}size-a[j]\kern{10pt}(a[j]<=size) //塞得下就直接塞。原容量为size,塞一个a[j]就是size-a[j]。\\w-a[j]\kern{21pt}(a[j]>\kern{8pt}size) //塞不下就重新开一个,这个组原容量为w,放了一个a[j]就是w-a[j]。\\\end{cases} 
#include<iostream>
using namespace std;
int a[1000005],f[1000005],size[1000005];
int main(){
    int n,w,i,j,ykb;
    cin>>n>>w;
    for(i=0;i<n;++i){
        cin>>a[i];
    }
    ykb=(1<<n);
    for(i=0;i<ykb;++i){
        f[i]=2147483647; //2147483647=2³¹-1,即int的最大存储范围。
    }
    f[0]=1; //至少要分1个组。
    size[0]=w; //容量就是w。因为我们什么东西都没放。
    for(i=0;i<ykb;++i){ //枚举所有状态。
        for(j=0;j<n;++j){
            if(i&(1<<j)){ //从左数第j位是1。即转移的相同,就直接跳过。
                continue;
            }
            if(size[i]>=a[j]){ //塞得下。
                if(f[i]<=f[i|(1<<j)]){ //如果f可以更新才会更新size。
                    f[i|(1<<j)]=f[i];
                    size[i|(1<<j)]=max(size[i|(1<<j)],size[i]-a[j]);
                }
            }else{  //塞不下。
                if(f[i]+1<=f[i|(1<<j)]){ //同上。
                    f[i|(1<<j)]=f[i]+1; //加1是因为要重新开一个组。
                    size[i|(1<<j)]=max(size[i|(1<<j)],w-a[j]);
                }
            }
        }
    }
    cout<<f[ykb-1]; //ykb为1<<n,减1则表示n个二进制位全是1。即所有物品都选。
    return 0;
}