插头DP小结-白红宇

插头DP小结

阅读量：5121 次

发布时间：2019-06-13

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

首先是CDQ《基于连通性状态压缩的动态规划问题》论文上的题目：

URAL 1519 Formula

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 const int maxn = 15;  6 const int HASH = 30007;  7 const int SIZE = 1000010;  8 typedef long long LL;  9 int N,M,maze[maxn][maxn],code[maxn],ch[maxn],ex,ey; 10 char b[maxn]; 11  12 struct Hashmap{ 13     int e,first[HASH],next[SIZE]; 14     LL state[SIZE],f[SIZE]; 15  16     void init(){ 17         e = 0; 18         memset(first,-1,sizeof(first)); 19     } 20  21     void push(LL st,LL ans){ 22         int h = st%HASH; 23         for(int i = first[h];i != -1;i = next[i]) 24         if(state[i] == st){ 25             f[i] += ans; 26             return; 27         } 28         state[e] = st; 29         f[e] = ans; 30         next[e] = first[h]; 31         first[h] = e++; 32     } 33 }dp[2]; 34  35 void update(int *code,int len){ 36     for(int i = len;i >= 1;i--) 37         code[i] = code[i-1]; 38     code[0] = 0; 39 } 40  41 void decode(int *code,int len,LL st){ 42     for(int i = len;i >= 0;i--){ 43         code[i] = st&7; 44         st >>= 3; 45     } 46 } 47  48 LL encode(int *code,int len){ 49     int cnt = 1; 50     memset(ch,-1,sizeof(ch)); 51     ch[0] = 0; 52     LL st = 0; 53     for(int i = 0;i <= len;i++){ 54         if(ch[code[i]] == -1){ 55             ch[code[i]] = cnt++; 56         } 57         code[i] = ch[code[i]]; 58         st <<= 3; 59         st |= code[i]; 60     } 61     return st; 62 } 63  64 void dpblank(int i,int j,int now,int pre){ 65     int left,up,t; 66     for(int k = 0;k < dp[pre].e;k++){ 67         decode(code,M,dp[pre].state[k]); 68         left = code[j-1],up = code[j]; 69  70         if(left && up){ 71             if(left == up){ 72                 if(i == ex && j == ey){ 73                     code[j-1] = code[j] = 0; 74                     if(j == M)  update(code,M); 75                     dp[now].push(encode(code,M),dp[pre].f[k]); 76                 } 77             } 78             else{ 79                 code[j-1] = code[j] = 0; 80                 for(t = 0;t <= M;t++){ 81                     if(code[t] == up)   code[t] = left; 82                 } 83                 if(j == M)  update(code,M); 84                 dp[now].push(encode(code,M),dp[pre].f[k]); 85             } 86         }else if((!left && up) ||(left && !up)){ 87             if(left) t = left; 88             else    t = up; 89             if(maze[i][j+1]){ 90                 code[j-1] = 0,code[j] = t; 91                 dp[now].push(encode(code,M),dp[pre].f[k]); 92             } 93             if(maze[i+1][j]){ 94                 code[j-1] = t,code[j] = 0; 95                 if(j == M)  update(code,M); 96                 dp[now].push(encode(code,M),dp[pre].f[k]); 97             } 98         }else{ 99             if(maze[i+1][j] && maze[i][j+1]){100                 code[j-1] = code[j] = 13;101                 dp[now].push(encode(code,M),dp[pre].f[k]);102             }103         }104     }105 }106 107 void dpblock(int i,int j,int now,int pre){108     for(int k = 0;k < dp[pre].e;k++){109         decode(code,M,dp[pre].state[k]);110         code[j-1] = code[j] = 0;111         if(j == M)  update(code,M);112         dp[now].push(encode(code,M),dp[pre].f[k]);113     }114 }115 116 int main()117 {118     while(scanf("%d%d",&N,&M) != EOF){119         memset(maze,0,sizeof(maze));120         ex = 0;121         for(int i = 1;i <= N;i++){122             scanf("%s",b+1);123             for(int j = 1;j <= M;j++)124                 if(b[j] == '.') maze[ex=i][ey=j] = 1;125         }126         if(ex == 0){127             printf("0\n");128             continue;129         }130         int now = 0,pre = 1;131         dp[now].init();132         dp[now].push(0,1);133         for(int i = 1;i <= N;i++){134             for(int j = 1;j <= M;j++){135                 swap(now,pre);136                 dp[now].init();137                 if(maze[i][j])  dpblank(i,j,now,pre);138                 else            dpblock(i,j,now,pre);139             }140         }141         LL ans = 0;142         for(int i = 0;i < dp[now].e;i++)143             ans += dp[now].f[i];144         printf("%I64d\n",ans);145     }146     return 0;147 }

View Code

POJ 1739 Tony's Tour

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 const int maxn = 15;  6 const int HASH = 30007;  7 const int SIZE = 1000010;  8 typedef long long LL;  9 int N,M,maze[maxn][maxn],code[maxn],ch[maxn],ex,ey; 10 char b[maxn]; 11  12 struct Hashmap{ 13     int e,first[HASH],next[SIZE]; 14     LL state[SIZE],f[SIZE]; 15  16     void init(){ 17         e = 0; 18         memset(first,-1,sizeof(first)); 19     } 20  21     void push(LL st,LL ans){ 22         int h = st%HASH; 23         for(int i = first[h];i != -1;i = next[i]) 24         if(state[i] == st){ 25             f[i] += ans; 26             return; 27         } 28         state[e] = st; 29         f[e] = ans; 30         next[e] = first[h]; 31         first[h] = e++; 32     } 33 }dp[2]; 34  35 void update(int *code,int len){ 36     for(int i = len;i >= 1;i--) 37         code[i] = code[i-1]; 38     code[0] = 0; 39 } 40  41 void decode(int *code,int len,LL st){ 42     for(int i = len;i >= 0;i--){ 43         code[i] = st&7; 44         st >>= 3; 45     } 46 } 47  48 LL encode(int *code,int len){ 49     int cnt = 1; 50     memset(ch,-1,sizeof(ch)); 51     ch[0] = 0; 52     LL st = 0; 53     for(int i = 0;i <= len;i++){ 54         if(ch[code[i]] == -1){ 55             ch[code[i]] = cnt++; 56         } 57         code[i] = ch[code[i]]; 58         st <<= 3; 59         st |= code[i]; 60     } 61     return st; 62 } 63  64 void dpblank(int i,int j,int now,int pre){ 65     int left,up,t; 66     for(int k = 0;k < dp[pre].e;k++){ 67         decode(code,M,dp[pre].state[k]); 68         left = code[j-1],up = code[j]; 69  70         if(left && up){ 71             if(left == up){ 72                 if(i == ex && j == ey){ 73                     code[j-1] = code[j] = 0; 74                     if(j == M)  update(code,M); 75                     dp[now].push(encode(code,M),dp[pre].f[k]); 76                 } 77             } 78             else{ 79                 code[j-1] = code[j] = 0; 80                 for(t = 0;t <= M;t++){ 81                     if(code[t] == up)   code[t] = left; 82                 } 83                 if(j == M)  update(code,M); 84                 dp[now].push(encode(code,M),dp[pre].f[k]); 85             } 86         }else if((!left && up) ||(left && !up)){ 87             if(left) t = left; 88             else    t = up; 89             if(maze[i][j+1]){ 90                 code[j-1] = 0,code[j] = t; 91                 dp[now].push(encode(code,M),dp[pre].f[k]); 92             } 93             if(maze[i+1][j]){ 94                 code[j-1] = t,code[j] = 0; 95                 if(j == M)  update(code,M); 96                 dp[now].push(encode(code,M),dp[pre].f[k]); 97             } 98         }else{ 99             if(maze[i+1][j] && maze[i][j+1]){100                 code[j-1] = code[j] = 13;101                 dp[now].push(encode(code,M),dp[pre].f[k]);102             }103         }104     }105 }106 107 void dpblock(int i,int j,int now,int pre){108     for(int k = 0;k < dp[pre].e;k++){109         decode(code,M,dp[pre].state[k]);110         code[j-1] = code[j] = 0;111         if(j == M)  update(code,M);112         dp[now].push(encode(code,M),dp[pre].f[k]);113     }114 }115 116 int main()117 {118     while(scanf("%d%d",&N,&M),N+M){119         memset(maze,0,sizeof(maze));120         for(int i = 1;i <= N;i++){121             scanf("%s",b+1);122             for(int j = 1;j <= M;j++)123                 if(b[j] == '.') maze[i][j] = 1;124         }125         maze[N+1][1] = maze[N+1][M] = 1;126         for(int i = 2;i < M;i++)    maze[N+1][i] = 0;127         for(int i = 1;i <= M;i++)   maze[N+2][i] = 1;128         N += 2;129         ex = N,ey = M;130 131         int now = 0,pre = 1;132         dp[now].init();133         dp[now].push(0,1);134         for(int i = 1;i <= N;i++){135             for(int j = 1;j <= M;j++){136                 swap(now,pre);137                 dp[now].init();138                 if(maze[i][j])  dpblank(i,j,now,pre);139                 else            dpblock(i,j,now,pre);140             }141         }142         LL ans = 0;143         for(int i = 0;i < dp[now].e;i++)144             ans += dp[now].f[i];145         printf("%I64d\n",ans);146     }147     return 0;148 }

View Code

UVA 10572 Black and White

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 const int HASH = 10007;  6 const int SIZE = 10000;  7 int N,M;  8 char maze[10][10];  9 int pre[65][SIZE],opt[65][SIZE]; 10  11 struct Hashmap{ 12     int e,first[HASH],next[SIZE]; 13     int color[SIZE],state[SIZE],f[SIZE]; 14  15     void init(){ 16         e = 0; 17         memset(first,-1,sizeof(first)); 18     } 19  20     void push(int st,int col,int ans,int id,int k,char ch){ 21         int h = ((st<<6)+col) % HASH; 22         for(int i = first[h];i != -1;i = next[i]) 23             if(state[i] == st && color[i] == col){ 24                 f[i] += ans; 25                 return; 26             } 27         state[e] = st; 28         color[e] = col; 29         f[e] = ans; 30         pre[id][e] = k; 31         opt[id][e] = ch; 32         next[e] = first[h]; 33         first[h] = e++; 34     } 35 }dp[2]; 36  37 int code[10],ch[10]; 38  39 void decode(int *code,int len,int st){ 40     for(int i = len-1;i >= 0;i--){ 41         code[i] = st&7; 42         st >>= 3; 43     } 44 } 45  46 int encode(int *code,int len){ 47     int st = 0,cnt = 0; 48     memset(ch,-1,sizeof(ch)); 49     for(int i = 0;i < len;i++){ 50         if(ch[code[i]] == -1) 51             ch[code[i]] = cnt++; 52         st = st<<3|ch[code[i]]; 53     } 54     return st; 55 } 56  57 void DP(int i,int j,int c,int now,int pre){ 58     for(int k = 0;k < dp[pre].e;k++){ 59         int col = dp[pre].color[k]; 60         int up = i ? ((col>>j)&1)==c : 0; 61         int left = j ? (col>>(j-1)&1)==c : 0; 62         int lu = (col>>M)== c; 63         if(up && left && lu)    continue; 64         if(i == N-1 && j == M-1 && !up && !left && lu)  continue; 65         decode(code,M,dp[pre].state[k]); 66         if(i && !up){ 67             int s1 = 0,s2 = 0; 68             for(int t = 0;t < M;t++){ 69                 if(code[t] == code[j])  s1++; 70                 if(((col>>t)&1) != c)   s2++; 71             } 72             if(s1 == 1){ 73                 if(s2 > 1)  continue; 74                 if(i < N-1 || j < M-2)  continue; 75             } 76         } 77         if(up && left){ 78             if(code[j] != code[j-1]){ 79                 for(int t = 0,x = code[j];t < M;t++) 80                     if(code[t] == x)    code[t] = code[j-1]; 81             } 82         } 83         else if(!up && left)    code[j] = code[j-1]; 84         else if(!up && !left)   code[j] = M; 85  86         if(col&(1<
         
          = 0;i--) 96         for(int j = M-1;j >= 0;j--) 97             maze[i][j] = opt[i*M+j][k],k = pre[i*M+j][k]; 98     for(int i = 0;i < N;i++)    puts(maze[i]); 99 }100 101 int main(){102     //freopen("input.txt","r",stdin);103     int kase;104     scanf("%d",&kase);105     while(kase--){106         scanf("%d%d",&N,&M);107         for(int i = 0;i < N;i++)108             scanf("%s",maze[i]);109         int now = 0,pre = 1;110         int ans = 0;111         dp[now].init();112         dp[now].push(0,0,1,0,0,0);113         for(int i = 0;i < N;i++)114             for(int j = 0;j < M;j++){115                 now ^= 1,pre ^= 1;116                 dp[now].init();117                 if(maze[i][j] != '#')   DP(i,j,0,now,pre);118                 if(maze[i][j] != 'o')   DP(i,j,1,now,pre);119             }120 121         int k;122         for(int i = 0;i < dp[now].e;i++){123             int tmp = 0;124             decode(code,M,dp[now].state[i]);125             for(int j = 0;j < M;j++)126                 tmp = max(tmp,code[j]);127             if(tmp > 1) continue;128             ans += dp[now].f[i],k = i;129         }130         printf("%d\n",ans);131         if(ans != 0)    print(k);132     }133     return 0;134 }

View Code

HYSBZ 1494 生成树计数

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 using namespace std;  6 const int N = 1<<6;  7 const int MOD = 65521;  8 int K,tot_status,f[N],fa[10];  9 int status[N],ord[1<<16]; 10 long long n; 11 struct Matrix{ 12     long long mat[N][N]; 13     Matrix operator*(const Matrix m)const{ 14         Matrix tmp; 15         for(int i = 0;i < tot_status;i++){ 16             for(int j = 0;j < tot_status;j++){ 17                 tmp.mat[i][j] = 0; 18                 for(int k = 0;k < tot_status;k++){ 19                     tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD; 20                     tmp.mat[i][j] %= MOD; 21                 } 22             } 23         } 24         return tmp; 25     } 26 }; 27  28 long long Pow(Matrix &m,long long n){ 29     Matrix ans; 30     memset(ans.mat,0,sizeof(ans.mat)); 31     for(int i = 0;i < tot_status;i++) 32         ans.mat[i][i] = 1; 33     n -= K; 34     while(n){ 35         if(n&1) ans = ans*m; 36         n >>= 1; 37         m = m*m; 38     } 39     long long sum = 0; 40     for(int i = 0;i < tot_status;i++){ 41         sum += ans.mat[0][i]*f[i]; 42         sum %= MOD; 43     } 44     return sum; 45 } 46  47 bool check(int st){ 48     int tmp = 0; 49     for(int i = 0;i < K;i++){ 50         int tp = (st>>(i*3))&7;tmp |= (1<
          
           <= tp;j++)  if(!(tmp&(1<
           
            <= K;i++) dfs(dep+1,st|(i<<(3*dep))); 62 } 63 64 int find(int x){ 65 return fa[x] == x ? x : fa[x] = find(fa[x]); 66 } 67 68 int main() 69 { 70 //freopen("output.txt","w",stdout); 71 scanf("%d%lld",&K,&n); 72 tot_status = 0; 73 dfs(1,1); 74 Matrix m; 75 memset(m.mat,0,sizeof(m.mat)); 76 for(int i = 0;i < tot_status;i++){ 77 f[i] = 1; 78 int cnt[10]; 79 memset(cnt,0,sizeof(cnt)); 80 for(int j = 0;j < K;j++) 81 cnt[status[i]>>(j*3)&7]++; 82 for(int j = 1;j <= K;j++){ 83 if(cnt[j] == 3) f[i] = 3; 84 if(cnt[j] == 4) f[i] = 16; 85 if(cnt[j] == 5) f[i] = 125; 86 } 87 for(int s = 0;s < (1<
            
             <= K;j++) fa[j] = j; 89 for(int j = 0;j < K;j++){ 90 for(int k = j+1;k < K;k++) 91 if(((status[i]>>(j*3))&7) == ((status[i]>>(k*3))&7)) 92 fa[find(j)] = find(k); 93 } 94 bool flag = 1; 95 for(int j = 0;j < K;j++)if(s&(1<
             
              <= K;j++)102 if(find(0) == find(j)){flag = 1;break;}103 if(!flag) continue;104 int use = 0,nxt = 0;105 for(int j = 0;j < K;j++)if(!(nxt&(7<<(j*3)))){106 nxt |= ++use<<(j*3);107 for(int k = j+1;k < K;k++)108 if(find(j+1) == find(k+1)) nxt |= use<<(k*3);109 }110 m.mat[ord[nxt]][i]++;111 }112 }113 printf("%lld\n",Pow(m,n));114 return 0;115 }

View Code

ZOJ 2125 Rocket Mania

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #define get(x,t) (((x) >> (t)) & 1)  5 #define get2(x,t) (((x) >> (t<<2)) &15)  6 const int HASH = 30007;  7 const int SIZE = 100000;  8 const int maxn = 10;  9 typedef long long LL; 10 struct Node{ 11     int s1; 12     LL s2; 13 }; 14 char map[maxn][maxn]; 15 int code[maxn],ch[maxn]; 16 Node best; 17 int last,n; 18 struct Hashmap{ 19     int e,first[HASH],next[SIZE]; 20     Node node[SIZE]; 21  22     void init(){ 23         e = 0; 24         memset(first,-1,sizeof(first)); 25     } 26  27     void push(int s1,LL s2){ 28         int h = abs(s1*s2+s1+s2) % HASH; 29         for(int i = first[h];i != -1;i = next[i]) 30             if(node[i].s1 == s1 && node[i].s2 == s2) 31                 return; 32         node[e].s1 = s1,node[e].s2 = s2; 33         next[e] = first[h]; 34         first[h] = e++; 35     } 36 }dp[2]; 37  38 void decode(int *code,LL st){ 39     for(int i = 0;i <= 9;i++,st >>= 4) 40         code[i] = st&15; 41 } 42  43 LL encode(int *code){ 44     LL st = 0; 45     int cnt = 1; 46     memset(ch,-1,sizeof(ch)); 47     for(int i = 9;i >= 0;i--){ 48         if(code[i] && ch[code[i]] == -1) 49             ch[code[i]] = cnt++; 50         if(code[i]) code[i] = ch[code[i]]; 51         st = st<<4; 52         st |= code[i]; 53     } 54     return st; 55 } 56  57 void update(int *code){ 58     for(int i = 9;i >= 1;i--) 59         code[i] = code[i-1]; 60     code[0] = 0; 61 } 62  63 int merge(int fire,int a,int b){ 64     int t = get(fire,a)|get(fire,b); 65     a = code[a],b = code[b]; 66     for(int i = 0;i <= 9;i++) 67         if(code[i] == b)   code[i] = a; 68     for(int i = 0;i <= 9;i++) 69         if(code[i] == a)   fire |= (t<
         
          <= 9;i++) 75     if(get2(t.s2,i) && !get(t.s1,i)){ 76         bool flag = 1; 77         for(int j = 0;j <= 9;j++) 78         if(i != j && get2(t.s2,i) == get2(t.s2,j)){ 79             flag = 0; 80             break; 81         } 82         if(flag)    t.s2 ^= (get2(t.s2,i)<<(i<<2)); 83     } 84     return t; 85 } 86  87 void insert(int s1,LL s2,int now){ 88     if(!s1) return; 89     bool flag = 1; 90     for(int i = 0;i <= 9;i++) 91     if(get2(s2,i) && !get(best.s1,i)){ 92         flag = 0;break; 93     } 94     if(flag)    return; 95     int tmp1 = 0,tmp2 = 0; 96     for(int i = 0;i <= 9;i++) 97         tmp1 += get(s1,i),tmp2 += get(best.s1,i); 98     if(tmp1 > tmp2) best.s1 = s1,best.s2 = s2; 99     if(last != -1){100         for(int i = 0;i <= last;i++)101         if(!get(s1,i) && get2(s2,i)){102             flag = 1;103             for(int t = last+1;t <= 9;t++)104                 if(get2(s2,i) == get2(s2,t)){105                     flag = 0;break;106                 }107             if(flag)    s2 ^= (get2(s2,i)<<(i<<2));108         }109         decode(code,s2),s2 = encode(code);110     }111     dp[now].push(s1,s2);112 }113 114 int DP(){115     int t = 1<
          
           < 9;i++){118         if(get(t,i))    code[i] = 1;119         else            code[i] = 0;120     }121     best.s1 = 0,best.s2 = 0;122     int now = 0,pre = 1;123     dp[now].init();124     insert(t,encode(code),now);125     last = -1;126     for(int j = -1;j < 6;j++){127         for(int i = j == -1 ? 8 : 0;i < 9;i++){128             now ^= 1,pre ^= 1;129             dp[now].init();130             best.s1 = best.s2 = 0;131 132             for(int k = 0;k < dp[pre].e;k++){133                 Node t = dp[pre].node[k];134                 t = check(t);135                 decode(code,t.s2);136                 if(i == 0){137                     update(code);138                     t.s2 = encode(code);139                     int tmp = get(t.s1,9);140                     t.s1 ^= (tmp << 9);141                     t.s1 <<= 1;142                 }143                 int up = code[i],left = code[i+1];144                 int a1 = get(t.s1,i),a2 = get(t.s1,i+1);145                 last = (j == 5 ? i : -1);146 147                 if(map[i][j] == '.'){148                     decode(code,t.s2);149                     code[i] = code[i+1] = 0;150                     insert(t.s1^(a1<
           
            <
            
             < dp[now].e;k++){262 Node t = dp[now].node[k];263 int tmp = 0;264 for(int i = 0;i < 9;i++)265 tmp += get(t.s1,i);266 ans = tmp > ans ? tmp : ans;267 }268 printf("%d\n",ans);269 }270 271 int main ()272 {273 while(scanf("%d",&n) != EOF){274 for(int i = 0;i < 9;i++)275 scanf("%s",map[i]);276 DP();277 }278 return 0 ;279 }