[APIO2007 zoo]状态压缩动态规划

【题目】http://www.oi.bbjy.com/n38c10.aspx

【算法分析】

这个比较好想，就是F[i][j]表示到达第i个点，状态为j的时候最多让多少个boy满意。

j是一个4位的2进制数，表示前面4个位置是搬走还是留下。在我的程序中，1表示搬走，0表示留下。

然后由于一个圈回来的时候连接的部分有些麻烦，所以直接枚举开始的4个位，然后再转移。

另外转移的部分比较纠结，我一开始用5个指针一起线性遍历，最慢的那个点变成3s+…..

然后后来围观了野牛的,发现他的快得很变态…..

呃,原来他用得位运算判重….

但是悲剧的是,我这个改了以后还是慢他的一倍

【其他】时间比较惨剧，在我学校的电脑里，不开任何东西，最慢那个点1.6s，开了-O999，变成0.8s

我也不知道为什么可以开-O999这东西。。。但是开-O999确实比开-O2快= =，那位神牛来解释一下这是啥？

【CODE】

#include #include const int N=51111;
const int INF=0x7FFFFFFF;
struct gtp{int y,next;}g[1001111];
int n,c,e,ans,hs,ls,times;
int p[N],love[N],hate[N],Hls[N],Lls[N],list[N],v[N];
int F[N][16];

inline int C(int x)          {if (x<0) x+=n; if (x>n) x-=n; return x;}
inline void addH(int x,int y) {e++; g[e].y=y; g[e].next=Hls[x]; Hls[x]=e;}
inline void addL(int x,int y) {e++; g[e].y=y; g[e].next=Lls[x]; Lls[x]=e;}
inline void max(int &x,int y) {if (y>x) x=y;}

void input(){
     scanf("%d%d",&n,&c);
     for (int i=1;i<=c;i++){
         int t1,t2,x;
         scanf("%d%d%d",&p[i],&t1,&t2);
         p[i]=C(p[i]+4);
         for (int j=1;j<=t1;j++){
             scanf("%d",&x);
             addH(x,i);
             hate[i]|=1<         }
         for (int j=1;j<=t2;j++){
             scanf("%d",&x);
             addL(x,i);
             love[i]|=1<         }
     }
}

int Cal(int i,int ns){
    int t,res;
    res=0;
    ns&=31;
    if (ns&1) t=Hls[i];
         else t=Lls[i];
    ns>>=1;
    for (;t;t=g[t].next){
        hs=hate[g[t].y]>>(C(p[g[t].y]-i)+1);
        ls=love[g[t].y]>>(C(p[g[t].y]-i)+1);
        if (hs&ns || ls&(INF^ns)) continue;
        res++;
    }
    return res;
}

void dp(int st){
     int i,ns,now,tmp;
     for (i=1;i<=n;i++)    
       for (ns=0;ns<16;ns++)
         F[i][ns]=-INF;
     F[5][(st<<1)&15]=Cal(5,st<<1);
     F[5][((st<<1)+1)&15]=Cal(5,(st<<1)+1);
     for (i=5;i       for (ns=0;ns<16;ns++)
         if (F[i][ns]!=-INF){
           max(F[i+1][(ns<<1)&15],F[i][ns]+Cal(i+1,ns<<1));
           max(F[i+1][((ns<<1)+1)&15],F[i][ns]+Cal(i+1,(ns<<1)+1));
         }
     for (ns=0;ns<16;ns++)
       if (F[n][ns]!=-INF){
         now=F[n][ns];
         now+=Cal(1,(ns<<1)+(st>>3));
         now+=Cal(2,(ns<<2)+(st>>2));
         now+=Cal(3,(ns<<3)+(st>>1));
         now+=Cal(4,(ns<<4)+(st>>0));
         ans>?=now;
       }
}

void count(){
     int now=0,i,res=0,t;
     times++;
     for (i=1;i<=n;i++)
       if (list[i]==0)
         for (t=Lls[i];t;t=g[t].next) v[g[t].y]=times;
       else
         for (t=Hls[i];t;t=g[t].next) v[g[t].y]=times;
     for (i=1;i<=c;i++)
       if (v[i]==times) res++;
     ans>?=res;
}

void dfs(int i){
     if (i>n){
       count();
       return;
     }
     list[i]=0;
     dfs(i+1);
     list[i]=1;
     dfs(i+1);
}

void work(){
     if (n>=5)
       for (int st=0;st<16;st++) dp(st);
     else dfs(1);
     printf("%dn",ans);
}

int main(){
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    input();
    work();
}