状压 \(dp\)

---

1、[SDOI2009]Bill的挑战

\(f[i][j]\) 表示匹配到字符串的第 \(i\) 位状态为 \(j\) 的方案数

那么方程就很明显了，每次枚举第 \(i\) 位的字母 \(alpha\) 然后 \(O(n)\) 判断就好了

时间复杂度 \(O(26Tlen2^nn)\)

\(Code\ Below:\)

#include 
    
     #define ll long longusing namespace std;const int p=1e6+3;int n,k,len,H[20],lg[1<<15],f[51][1<<15];char s[16][51];inline int read(){    register int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return (f==1)?x:-x;}int main(){    register int T=read(),i,j,k,t,now,l,ans;    H[0]=1;    for(i=1;i<32768;i++) lg[i]=lg[i>>1]+(i&1);    for(i=1;i<20;i++) H[i]=H[i-1]<<1;    while(T--){        n=read(),k=read();        for(i=1;i<=n;i++) scanf("%s",s[i]+1);        if(n
     
      =k){                    for(t=0;t<26;t++){                        now=0;                        for(l=1;l<=n;l++)                            if((j&H[l-1])&&(s[l][i]=='?'||s[l][i]==t+'a')) now|=H[l-1];                        f[i][now]=(f[i][now]+f[i-1][j])%p;                    }                }        ans=0;        for(int i=0;i
     
    

2、[SDOI2009]学校食堂

状压 \(dp\) 好题！

首先 \(a\ or\ b - a\ and\ b = a\ xor\ b\)

\(f[i][j][k]\) 表示到第 \(i\) 个人状态为 \(j\) 最后一个打饭的编号为 \(i+k\) 的方案数

那么就可以转移了

if(j&1) chkmin(f[i+1][j>>1][k+7],f[i][j][k+8]);else {    int lim=inf;    for(int l=0;l<=7;l++){        if(!(j&(1<
    
     lim) break;            chkmin(lim,i+l+B[i+l]);            chkmin(f[i][j|(1<
    

\(Code\ Below:\)

#include 
    
     using namespace std;const int maxn=1000+10;const int inf=0x3f3f3f3f;int n,T[maxn],B[maxn],f[maxn][1<<8][16];inline int read(){    register int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return (f==1)?x:-x;}inline void chkmin(int &a,int b){a=a
     
      >1][k+7],f[i][j][k+8]);                    else {                        int lim=inf;                        for(int l=0;l<=7;l++){                            if(!(j&(1<
      
       lim) break;                                chkmin(lim,i+l+B[i+l]);                                chkmin(f[i][j|(1<
      
     
    

3、[CQOI2018]解锁屏幕

\(check\) 好麻烦啊

\(Code\ Below\):

#include 
    
     #define res register intusing namespace std;const int p=1e8+7;int n,x[20],y[20],H[20],a[20][20],dp[1<<20][20],vis[1<<20][20],ans;int head=1,tail=0,q[(1<<20)*20*2+10];int check(int k,int f,int j){    if(k==f||k==j) return 0;    if(x[f]==x[k]||x[f]==x[j]){        if(x[f]==x[k]&&x[f]==x[j]&&(y[f]<=y[k])==(y[k]<=y[j])) return 1;        if(y[f]==y[k]&&y[f]==y[j]&&(x[f]<=x[k])==(x[k]<=x[j])) return 1;        return 0;    }    if((x[f]<=x[k])==(x[k]<=x[j])&&(y[f]<=y[k])==(y[k]<=y[j])&&(y[f]-y[k])*(x[f]-x[j])==(y[f]-y[j])*(x[f]-x[k])) return 1;    return 0;}void add(res &x,const res &y){    x=x+y
     
      =4) add(ans,dp[i][f]);        for(j=0;j