HDU3377 Plan

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3377
简单路径要求权值最大，那么为了回避括号序列单独插头的情况特判多，考虑使用最小表示法。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 using namespace std;
  9 #define maxn 21
 10 #define inf ((0x7fffffff)-1)
 11 #define llg int
 12 #define sizee 233
 13 #define maxnZT ((1<<20)+1)
 14 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 15 llg n,m,code[maxn],zt[2][maxnZT],v[2][maxnZT],g[110][110],size[2],now,ne,ans=inf*-1;
 16 llg maze[10][10],val[10][10],ch[22];
 17 void outcode(llg x){for (llg i=0;i<=m;i++) code[i]=x&3,x>>=2;}
 18 
 19 struct node
 20 {
 21     llg x,val,pos;
 22 };
 23 
 24 vector<node>a[2][sizee];
 25 
 26 void decode(llg x) {for (llg i=0;i<=m;i++) code[i]=x&7,x>>=3;}
 27 
 28 void encode(llg p,llg val)
 29 {
 30     for (llg i=0;i<=20;i++) ch[i]=-1;
 31     ch[0]=0;
 32     llg C=0;
 33     for (llg i=0;i<=m;i++)
 34     {
 35         if (ch[code[i]]==-1) ch[code[i]]=++C;
 36         code[i]=ch[code[i]];
 37     }
 38     llg x=0;
 39     for (llg i=0;i<=m;i++) x+=code[i]*(1<<(i*3));
 40     llg wz=x%sizee,E=a[p][wz].size();
 41     for (llg i=0;i<E;i++)
 42         if (a[p][wz][i].x==x)
 43         {
 44             a[p][wz][i].val=max(a[p][wz][i].val,val);
 45             v[p][a[p][wz][i].pos]=max(v[p][a[p][wz][i].pos],val);
 46             return ;
 47         }
 48     size[p]++;
 49     node NEW; NEW.x=x; NEW.val=val; NEW.pos=size[p];
 50     a[p][wz].push_back(NEW);
 51     zt[p][size[p]]=x; v[p][size[p]]=val;
 52 }
 53 
 54 void init_a(llg p){for (llg i=0;i<sizee;i++) a[p][i].clear(); size[p]=0;}
 55 
 56 
 57 void shift()///换行 移位
 58 {
 59     for(int i=m;i>0;i--)
 60         code[i]=code[i-1];
 61     code[0]=0;
 62 }
 63 
 64 
 65 void dp(llg x,llg y)
 66 {
 67     llg left,up,V;
 68     for (llg K=1;K<=size[now];K++)
 69     {
 70         decode(zt[now][K]);
 71         left=code[y-1],up=code[y];//左上插头
 72         V=v[now][K];
 73 //------------------------------------------------------------
 74         if ((x==1 && y==1))//开始位置
 75         {
 76             if (maze[x][y+1])//往左走
 77             {
 78                 code[y]=17,code[y-1]=0;
 79                 encode(ne,V+val[x][y]);
 80             }
 81             if (maze[x+1][y])//往下走
 82             {
 83                 code[y-1]=17,code[y]=0;
 84                 encode(ne,V+val[x][y]);
 85             }
 86             continue;
 87         }
 88 //------------------------------------------------------------
 89         if (x==n && y==m)//结束位置
 90         {
 91             if ((!left && up) || (left && !up))//必须有且仅有一个插头
 92             {
 93                 code[y]=code[y-1]=0;
 94                 bool pd=true;
 95                 for (llg t=0;t<=m;t++) if (code[t]) pd=false;
 96                 if (pd) ans=max(ans,V+val[x][y]);
 97             }
 98             continue;
 99         }
100 //------------------------------------------------------------
101         if (left && up)//插头合并
102         {
103             if (left!=up)//如果属于同一个连通块则非法(因为形成了环)
104             {
105                 code[y]=code[y-1]=0;
106                 for (llg t=0;t<=m;t++) if (code[t]==up) code[t]=left;
107                 if (y==m) shift();
108                 encode(ne,V+val[x][y]);
109             }
110             continue;
111         }
112 //------------------------------------------------------------
113         if (left || up)//延续原来的连通分量
114         {
115             llg tmp;
116             if (left) tmp=left;else tmp=up;
117             if (maze[x][y+1])
118             {
119                 code[y-1]=0,code[y]=tmp;
120                 encode(ne,V+val[x][y]);
121             }
122             if (maze[x+1][y])
123             {
124                 code[y-1]=tmp,code[y]=0;
125                 if (y==m) shift();
126                 encode(ne,V+val[x][y]);
127             }
128         }
129 //------------------------------------------------------------
130         if (!left && !up)//没有插头，新建连通分量或者不走这一个格子
131         {
132             if (maze[x][y+1] && maze[x+1][y])
133             {
134                 code[y]=code[y-1]=17;
135                 encode(ne,V+val[x][y]);
136             }
137             code[y]=code[y-1]=0;
138             if (y==m) shift();
139             encode(ne,V);
140         }
141     }
142 }
143 
144 void work()
145 {
146     now=0,ne=0;
147     encode(now,0);
148     for (llg i=1;i<=n;i++)
149     {
150         for (llg j=1;j<=m;j++)
151         {
152             ne=now^1;
153             init_a(ne);
154             dp(i,j);
155             now=ne;
156         }
157     }
158 }
159 
160 void init()
161 {
162     memset(maze,0,sizeof(maze));
163     for (llg i=1;i<=n;i++) 
164         for (llg j=1;j<=m;j++)
165             scanf("%d",&val[i][j]),maze[i][j]=1;
166 }
167 
168 int main()
169 {
170     yyj("hdu3377");
171     llg cas=0;
172     while (scanf("%d%d",&n,&m)!=EOF)
173     {
174         ans=inf*-1;
175         cas++;
176         init();
177         if (n==1 && m==1) 
178         {
179             printf("Case %d: %d
",cas,val[n][m]);
180             init_a(1),init_a(0);
181             continue;
182         }
183         work();
184         printf("Case %d: %d
",cas,ans);
185         init_a(1),init_a(0);
186     }
187     return 0;
188 }