USACO 状压DP练习[3]-白红宇

USACO 状压DP练习[3]

阅读量：6918 次

发布时间：2019-06-27

本文共 2212 字，大约阅读时间需要 7 分钟。

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

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

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           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

View Code

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

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

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           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
           
            k ) f[i][s]+=f[j][t]; } ll ans=0; for(int i=0;i

View Code

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

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

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

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          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<
          
           =0;j--) f[j|a[i]]=max(f[j|a[i]],f[j]+1); int ans=0; for(int j=0;j