Ural1519 Formula 1(插头dp）-白红宇

Ural1519 Formula 1(插头dp）

阅读量：6232 次

发布时间：2019-06-21

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

原题网址：

有关插头dp和状态压缩请参考：

详细代码（c++11）：采用括号表示法和最小表示法两种实现方式

注意：使用最小表示法时，数据类型要用到long long（__int64), 相应的移位要用long long进行，用int会溢出！

1. hasp_map（括号表示法）

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 // using namespace std; 6 using namespace __gnu_cxx; 7  8 typedef long long LL; 9 const int MAXRC = 15, MAXSTATE=3001;10 int m,n,er=-1,ec, idx=0;11 int city[MAXRC][MAXRC]={
   0}, bits_at[MAXRC];// 1 is valid.12 hash_map
         
           hm[2];13 14 inline int get_state_at(int s, int j){15     return (s&bits_at[j])>>(j<<1);16 }17 inline int set_state_at(int s, int j, int b){18     s &= ~(bits_at[j]);19     return s|(b<<(j<<1));20 }21 inline int set_state_at(int s, int j, int bj, int bn){22     s &= ~(bits_at[j]+bits_at[j+1]);23     s |= (bj+(bn<<2))<<(j<<1);24     return s;25 }26 int find_match(int s, int j){
   // c!=027     int c = get_state_at(s, j), d = c == 1? 1:-1, f = 0;28     for(;;j+=d){29         if(get_state_at(s, j)==c) f++;30         else if(get_state_at(s,j)) f--;31         if(f == 0) return j;32     }33     return -1;34 }35 void dp(){36     idx = 0;hm[idx].clear();hm[idx][0]=1;37     for(int i=0; i
          
           ::iterator it=hm[idx].begin();42 for(; it!=hm[idx].end(); ++it){43 LL ps = it->first, pn = it->second;44 if(j == 0) ps <<=2;45 int sl = get_state_at(ps, j), su = get_state_at(ps, j+1);46 if(sl == 0 && su == 0){47 if(!city[i][j]){ // 将状态延伸到非 . 处48 hm[cur][set_state_at(ps, j, 0, 0)] += pn;49 }// 插头应该指向空白的格子50 else if(city[i][j+1] && city[i+1][j]){51 hm[cur][set_state_at(ps, j, 1, 2)] += pn;52 }53 }54 else if(sl == 0 || su == 0){ // 只延伸一个插头55 if(city[i][j+1]) 56 hm[cur][set_state_at(ps, j, 0, sl+su)] += pn;57 if(city[i+1][j])58 hm[cur][set_state_at(ps, j, sl+su, 0)] += pn;59 }60 else if(sl == su){ // 合并连通块，同时左括号或右括号61 int posl = find_match(ps, j), posu = find_match(ps, j+1);62 int mn = std::min(posl, posu), mx = std::max(posl, posu);63 LL cs = set_state_at(ps, mn, 1);64 cs = set_state_at(cs, mx, 2);65 hm[cur][set_state_at(cs, j, 0, 0)] += pn;66 }67 else if(sl == 2 && su == 1){ // 合并成简单路径68 hm[cur][set_state_at(ps, j, 0, 0)] += pn;69 }70 else if(i == er && j == ec){ // 合并成回路，只在最后一个有效的格子71 hm[cur][set_state_at(ps, j, 0, 0)] += pn;72 }73 }74 idx = cur;// 交换状态 75 }76 }77 }78 int main(){79 freopen("in.txt", "r", stdin);80 scanf("%d%d", &n, &m);81 char cy[MAXRC][MAXRC];82 for(int i=0; i

2.map（括号表示法）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 // #include 
         
           5 #include 
           6 // using namespace std; 7 using namespace __gnu_cxx; 8  9 typedef long long LL;10 const int MAXRC = 15, MAXSTATE=3001;11 int m,n,er=-1,ec, idx=0;12 int city[MAXRC][MAXRC]={
    0}, bits_at[MAXRC];// 1 is valid.13 std::map
           
             mp[2];14 15 inline int get_state_at(LL s, int j){16 return (s&bits_at[j])>>(j<<1);17 }18 inline LL set_state_at(LL s, int j, int b){19 s &= ~(bits_at[j]);20 return s|(b<<(j<<1));21 }22 inline LL set_state_at(LL s, int j, int bj, int bn){23 s &= ~(bits_at[j]+bits_at[j+1]);24 s |= (bj+(bn<<2))<<(j<<1);25 return s;26 }27 int find_match(LL s, int j){ // c!=028 int c = get_state_at(s, j), d = c == 1? 1:-1, f = 0;29 for(;;j+=d){30 if(get_state_at(s, j)==c) f++;31 else if(get_state_at(s,j)) f--;32 if(f == 0) return j;33 }34 return -1;35 }36 void dp(){37 idx = 0;mp[idx].clear();mp[idx][0]=1;38 for(int i=0; i
            
             ::iterator it=mp[idx].begin();43 for(; it!=mp[idx].end(); ++it){44 LL ps = it->first, pn = it->second;45 if(j == 0) ps <<=2;46 LL sl = get_state_at(ps, j), su = get_state_at(ps, j+1);47 if(sl == 0 && su == 0){48 if(!city[i][j]){ // 将状态延伸到非 . 处49 mp[cur][set_state_at(ps, j, 0, 0)] += pn;50 }// 插头应该指向空白的格子51 else if(city[i][j+1] && city[i+1][j]){52 mp[cur][set_state_at(ps, j, 1, 2)] += pn;53 }54 }55 else if(sl == 0 || su == 0){ // 只延伸一个插头56 if(city[i][j+1]) 57 mp[cur][set_state_at(ps, j, 0, sl+su)] += pn;58 if(city[i+1][j])59 mp[cur][set_state_at(ps, j, sl+su, 0)] += pn;60 }61 else if(sl == su){ // 合并连通块，同时左括号或右括号62 int posl = find_match(ps, j), posu = find_match(ps, j+1);63 int mn = std::min(posl, posu), mx = std::max(posl, posu);64 LL cs = set_state_at(ps, mn, 1);65 cs = set_state_at(cs, mx, 2);66 mp[cur][set_state_at(cs, j, 0, 0)] += pn;67 }68 else if(sl == 2 && su == 1){ // 合并成简单路径69 mp[cur][set_state_at(ps, j, 0, 0)] += pn;70 }71 else if(i == er && j == ec){ // 合并成回路，只在最后一个有效的格子72 mp[cur][set_state_at(ps, j, 0, 0)] += pn;73 }74 }75 idx = cur;// 交换状态 76 }77 }78 }79 int main(){80 freopen("in.txt", "r", stdin);81 scanf("%d%d", &n, &m);82 char cy[MAXRC][MAXRC];83 for(int i=0; i

View Code

3.map（最小表示法）

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 using namespace std;  6   7 typedef long long LL;  8 int m,n,er=-1,ec=0,idx = 0,  9     valid[15][15] = {
    0}, mk[8];// er,ec最后一个有效的位置 10  11 map
          
            mp[2];// pair: state,sum 12 LL mask_one=07; 13  14 int get_state(LL st, int i){
    // 获取第i个位置的状态 15     return (st&(mask_one<
           
            >i*3; 16 } 17 void set_state(LL &s, int i, LL ns){ // 设置第i个位置的状态 18 s &= ~(mask_one<<3*i); 19 s |= ns << 3*i; 20 } 21 void set_state(LL &s, int i, LL sj, LL su){ 22 set_state(s, i, sj); 23 set_state(s, i+1, su); 24 } 25 LL rearrange(LL s){ // 调整状态，使连通块按从小到大的顺序排列 26 memset(mk, -1, sizeof mk); 27 mk[0] = 0; 28 int cnt=1; 29 for(int i=0; i<=m; ++i){ 30 int st = get_state(s, i); 31 if(mk[st] == -1) mk[st] = cnt++; 32 } 33 for(int i=0; i<=m; ++i){ 34 int st = get_state(s, i); 35 if(mk[st] != st) set_state(s, i, mk[st]); 36 } 37 return s; 38 } 39 void dp(){ 40 mp[0].clear(); mp[1].clear(); idx = 0; 41 mp[idx][0] = 1; 42 for(int i=0; i
            
             ::iterator it = mp[idx].begin(); 47 for(;it!=mp[idx].end(); ++it){ 48 LL s = it->first, n = it->second; 49 if(j == 0) s<<=3; 50 int su = get_state(s, j+1), sl = get_state(s, j);// 格子的左方向和上方向的插头状态 51 if(su==0 && sl==0){ 52 if(!valid[i][j]){ // 遇到无效格子进行延伸状态 53 set_state(s, j, 0, 0); 54 mp[cur][s] += n; 55 } 56 else if(valid[i][j+1]&&valid[i+1][j]){ // 新建连通块 57 set_state(s, j, 7, 7); 58 mp[cur][rearrange(s)] += n; 59 } 60 } 61 else if(sl == 0 || su == 0){ // 延伸单个连通块 62 if(valid[i][j+1]){ 63 set_state(s, j, 0, su+sl); 64 mp[cur][s] += n; 65 } 66 if(valid[i+1][j]){ 67 set_state(s, j, su+sl, 0); 68 mp[cur][s] += n; 69 } 70 } 71 else if(su != sl){ // 合并不同的连通块 72 int nb = min(su,sl), mb = max(su, sl); 73 set_state(s, j, 0, 0); 74 for(int k=0; k
             
               mb) set_state(s, k, ts-1); 79 } 80 mp[cur][s] += n; 81 } 82 else if(i==er && j==ec){ // 最后一个有效的格子合并成回路 83 set_state(s, j, 0, 0); 84 mp[cur][s] += n; 85 } 86 } 87 idx = cur;// 交换状态 88 } 89 } 90 } 91 int main() { 92 freopen("in.txt", "r", stdin); 93 char city[14][14]; 94 scanf("%d%d", &n, &m); 95 for(int i=0; i

View Code

4.人工hashmap

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 // using namespace std;  5   6 typedef long long LL;  7 const int MAXRC = 15, MAXSTATE=300001;  8 int m,n,er=-1,ec, idx=0;  9 int city[MAXRC][MAXRC]={
    0}, bits_at[MAXRC];// 1 is valid. 10  11 class Hashmap{ 12 public: 13     int head[MAXSTATE], nxt[MAXSTATE], size; 14     LL state[MAXSTATE], num[MAXSTATE]; 15     void init(){ 16         size = 0; 17         memset(head, -1, sizeof head); 18         // memset(nxt, -1, sizeof nxt);// 头插法不用初始化nxt 19     } 20     void push(LL s, LL n){ 21         int pos = s%MAXSTATE, bg = head[pos]; 22         while(bg != -1){ 23             if(state[bg]==s){ 24                 num[bg] += n; 25                 return ; 26             } 27             bg = nxt[bg]; 28         } 29         state[size] = s; 30         num[size] = n; 31         // 头插法 32         nxt[size] = head[pos]; 33         head[pos] = size++; 34     } 35 }hm[2]; 36  37 inline int get_state_at(LL s, int j){ 38     return (s&bits_at[j])>>(j<<1); 39 } 40 inline LL set_state_at(LL s, int j, int b){ 41     s &= ~(bits_at[j]); 42     return s|(b<<(j<<1)); 43 } 44 inline LL set_state_at(LL s, int j, int bj, int bn){ 45     s &= ~(bits_at[j]+bits_at[j+1]); 46     s |= (bj+(bn<<2))<<(j<<1); 47     return s; 48 } 49 int find_match(LL s, int j){
    // c!=0 50     int c = get_state_at(s, j), d = c == 1? 1:-1, f = 0; 51     for(;;j+=d){ 52         if(get_state_at(s, j)==c) f++; 53         else if(get_state_at(s,j)) f--; 54         if(f == 0) return j; 55     } 56     return -1; 57 } 58 void dp(){ 59     idx = 0;hm[idx].init();hm[idx].push(0,1); 60     for(int i=0; i
         
          0?hm[idx].num[0]:0LL);119     return 0;120 }