USACO 状压DP练习[3]

题意：$m*n: m,n le 12$的牧场，有的格子不能选，相邻不能同时选，求方案数

$f[i][j]$前$i$行当前行选的集合为$j$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=13,S=(1<<12)+5,P=1e8;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int m,n;
int f[N][S],cant[N];
inline void mod(int &x){if(x>=P) x-=P;}
int main(){
    //freopen("in","r",stdin);
    m=read();n=read();
    for(int i=1;i<=m;i++)
        for(int j=0;j<n;j++) if(!read()) cant[i]|=(1<<j);
    int All=1<<n;
    f[0][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=0;j<All;j++) if( (j&(j<<1))==0 && (j&cant[i])==0 )
            for(int k=0;k<All;k++) if( (k&(k<<1))==0 && (k&cant[i-1])==0 && (k&j)==0 )
                f[i][j]+=f[i-1][k];
    int ans=0;  
    for(int j=0;j<All;j++) if( (j&(j<<1))==0 && (j&cant[m])==0 ) mod(ans+=f[m][j]);
    printf("%d",ans);
}

View Code

1231

题意：$n le 16$个数字排列，所有相邻数字相差$ge k$的方案数

$f[i][j]$表示当前已经选上的数字集合为$j$,以第$i$个数字结尾的方案数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=18,S=(1<<16)+5,P=1e8;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
 
int n,k,a[N];
ll f[N][S];
int main(){
    //freopen("in","r",stdin);
    n=read();k=read();
    for(int i=0;i<n;i++) a[i]=read(),f[i][1<<i]=1;
    int All=1<<n;
    for(int s=0;s<All;s++)
        for(int i=0;i<n;i++) if((1<<i)&s){
            int t=s^(1<<i);
            for(int j=0;j<n;j++) if( ((1<<j)&t) && abs(a[i]-a[j])>k ) f[i][s]+=f[j][t];
        }
    ll ans=0;
    for(int i=0;i<n;i++) ans+=f[i][All-1];
    printf("%lld",ans);
}

View Code

1688

题意：有N头牛,它们可能患有D种病,现在从这些牛中选出若干头来,但选出来的牛患病的集合中不过超过K种病,最多选几头

$f[i][s]$表示前$i$头病集合为$j$最多选几头

用更新的写法比较好，因为你不知道去掉第$i$头后其他牛有没有第$i$头牛的病，还得预处理之类的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1005,S=(1<<15)+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,m,k,a[N],f[S];
inline int bitCount(int n){
    int c=0;
    for(;n;++c) n&=(n-1);
    return c;
}
int main(){
    //freopen("in","r",stdin);
    n=read();m=read();k=read();
    for(int i=1;i<=n;i++){
        int c=read();
        while(c--) a[i]|= 1<<(read()-1);
    }
    int All=1<<m;
    for(int i=1;i<=n;i++)
        for(int j=All-1;j>=0;j--) 
            f[j|a[i]]=max(f[j|a[i]],f[j]+1);
    int ans=0;
    for(int j=0;j<All;j++) 
        if(bitCount(j)<=k) ans=max(ans,f[j]);
    printf("%d",ans);
}