题解 P3052 【[USACO12MAR]Cows in a Skyscraper G】
xh39
2020-03-04 10:39:03
注:本题解物品已经其他的下标都是从**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}$
```cpp
#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;
}
```