UOJ370 滑稽树上滑稽果 【状压DP】

题目分析：

答案肯定是链，否则可以把枝干放到主干。

去除一直存在的位，这样0位占满时就会结束。

用$f[S]$表示0位填埋情况，每次转移是它的一个子集，我们考虑可否转移。

再用$g[S]$存储转移是否合法，用滑稽果填充$g$数组。不一定要完全满足条件，因为有其它方案更优，无影响。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define RI register

 const int maxn = ;

 int n,a[maxn],bit=,maxx;

 long long ans = ;

 int cnt = (<<)-,res=;

 int f[<<];

 int g[<<],vol[<<];

 char buffer[], *buf=buffer;

 inline void in(int &x) {

     while(*buf>'' || *buf<'') ++buf;

     for(x=;*buf>=''&&*buf<=''; ++buf) x=x*+*buf-'';

 }

 inline void read(){

     in(n);

     for(RI int i=;i<=n;i++) in(a[i]),cnt &= a[i];

     for(RI int i=;i<=n;i++) a[i] -= cnt,maxx=max(maxx,a[i]),res |= a[i];

     ans += 1ll*cnt*n;

 }

 inline void init(){

     while((bit<<)<=maxx)bit<<=; bit<<=; res = (bit--res);

     for(RI int i=;i<=n;i++) vol[bit--a[i]]=;

     for(RI int i=bit-;i>=;i--){

     if(!vol[i] || g[i]) continue;

     for(RI int j=i;j;j=((j-)&i)){g[j]=;}

     }

 }

 inline void work(){

     memset(f,0x3f,sizeof(f)); f[] = ;

     for(RI int now=;now<bit;now++){

     if(f[now] > 1e6) continue;

     int dt = bit--now;

     for(RI int i=dt;i;i=((i-)&dt)){

         if(g[i]){f[now+i] = min(f[now+i],f[now]+bit--(now+i));};

     }

     }

     ans += f[bit-];

     printf("%lld",ans);

 }

 int main(){

     fread(buffer, , (sizeof buffer)-, stdin);

     read();

     init();

     work();

     return ;

 }