bzoj1294题解

 1 #pragma GCC optimize(2)
 2 #include <algorithm>
 3 #include <cctype>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <functional>
 7 #include <vector>
 8 #define REP(i,low,high) for(register int i=(low);i<=(high);++i)
 9 #define PER(i,high,low) for(register int i=(high);i>=(low);--i)
10 using namespace std;
11  
12 //ex_cmp {
13 template<typename T,class Compare> inline bool getcmp(T &target,const T &pattern,Compare comp)
14 {
15     return comp(pattern,target)?target=pattern,1:0;
16 }
17 //} ex_cmp
18  
19 static const int N=204800,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; vector<int> line[20];
20 static int n,m,d,ans=0,dfn=0; bool map[20][20]={0},inq[20][20][512];
21 int val[20],bx[20],qx[N],qy[N],qz[N],f[20][20][512],vis[20][20][512]={0};
22 inline int &move(int &x) {return ++x==N?x=0:x;}
23 inline bool cmp(const int &one,const int &another) {return bx[one]>bx[another];}
24 inline void SPFA(const int &sx,const int &sy)
25 {
26     vis[sx][sy][f[qx[0]=sx][qy[0]=sy][qz[0]=0]=0]=++dfn; for(int head=-1,tail=0;head!=tail;)
27     {
28         move(head); int frx=qx[head],fry=qy[head],frz=qz[head];
29         if(frx==sx&&fry==sy) getcmp(ans,f[frx][fry][frz],greater<int>()); REP(i,0,3)
30         {
31             int tox=frx+dx[i],toy=fry+dy[i]; if(tox&&toy&&tox<=n&&toy<=m&&!map[tox][toy])
32             {
33                 int toz=frz,det=0; if(i<2)
34                 {
35                     int x,y; toy>fry?(x=tox,y=toy):(x=frx,y=fry); PER(j,line[y].size()-1,0)
36                     {
37                         int dig=line[y][j]; if(bx[dig]>=x) break;
38                         int bin=1<<dig-1; det+=(toz&bin?-1:1)*val[dig],toz^=bin;
39                     }
40                 }
41                 if(vis[tox][toy][toz]!=dfn||f[frx][fry][frz]+det-1>f[tox][toy][toz])
42                 {
43                     f[tox][toy][toz]=f[frx][fry][frz]+det-1,vis[tox][toy][toz]=dfn;
44                     if(!inq[tox][toy][toz]) move(tail),inq[qx[tail]=tox][qy[tail]=toy][qz[tail]=toz]=1;
45                 }
46             }
47         }
48         inq[frx][fry][frz]=0;
49     }
50 }
51 int main()
52 {
53     scanf("%d%d%d",&n,&m,&d),memset(line,0,sizeof line),memset(f,0xfe,sizeof f); REP(i,1,d) scanf("%d",val+i);
54     REP(i,1,n) REP(j,1,m)
55     {
56         char ch=getchar(); for(;isspace(ch)||ch==‘\n‘;ch=getchar()); int num=ch-‘0‘; switch(ch)
57         {
58             case ‘0‘:break; case ‘#‘:map[i][j]=1; break; default:map[bx[num]=i][j]=1,line[j].push_back(num);
59         }
60     }
61     REP(i,1,m) sort(line[i].begin(),line[i].end(),cmp); REP(i,1,n) REP(j,1,m) if(!map[i][j]) SPFA(i,j);
62     return printf("%d\n",ans),0;
63 }