题解 P3052 【[USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper】

feecle6418 · 2019-08-22 20:51:52 · 题解

UPD：修正时间复杂度

这里有一种非正解的方法。

状压DP，f[S] 表示达到状态 S 需要分成的最小组数，其中 S 第 i 位表示第 i 个数是否已经选过。首先预处理出 s[S] 表示状态 S 中所有树的和。那么转移方程为：

于是暴力转移即可。复杂度为 O(3^n)，要超时，但是吸氧之后能过。

不会枚举子集？你只需记住以下代码：（建议手动模拟加深印象qwq）

for(int j=i;j;j=(j-1)&i)//do something

代码：

// luogu-judger-enable-o2
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
using namespace std;
int n,a[20];
int f[300005],s[300005],ans,K;
int main(){
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<(1<<n);i++){
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1)))s[i]+=a[j];
        }
    }
    for(int i=1;i<(1<<n);i++){
        for(int j=i;j;j=(j-1)&i){
            if(s[j]>K)continue;
            f[i]=min(f[i],f[i-j]+1);
        }
    }
    printf("%d\n",f[(1<<n)-1]);
    return 0;
}