【题意分析】
给定一张网格图，每个网格可能是普通点、特殊点或障碍点，每个特殊点有一个分值。要求选定一条只经过普通点的可重复回路，使回路内部的特殊点分值和最大。
【算法分析】
引理：射线法
对于平面内任意一点P，向x轴方向引一条射线l，若l与一封闭曲线m的交点数为奇，则P必定在封闭曲线m所围成的封闭图形内，反之则P必定在其外。
考虑状态压缩DP，f[i][j][k]表示当前在点(i,j)并且豆豆的二进制状态为k时获得的最大分值。由于此DP的阶段比较特殊，故需要用SPFA进行转移。
【参考代码】
#pragma GCC optimize(2) #include <algorithm> #include <cctype> #include <cstdio> #include <cstring> #include <functional> #include <vector> #define REP(i,low,high) for(register int i=(low);i<=(high);++i) #define PER(i,high,low) for(register int i=(high);i>=(low);--i) using namespace std; //ex_cmp { template<typename T,class Compare> inline bool getcmp(T &target,const T &pattern,Compare comp) { return comp(pattern,target)?target=pattern,1:0; } //} ex_cmp static const int N=204800,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; vector<int> line[20]; static int n,m,d,ans=0,dfn=0; bool map[20][20]={0},inq[20][20][512]; int val[20],bx[20],qx[N],qy[N],qz[N],f[20][20][512],vis[20][20][512]={0}; inline int &move(int &x) {return ++x==N?x=0:x;} inline bool cmp(const int &one,const int &another) {return bx[one]>bx[another];} inline void SPFA(const int &sx,const int &sy) { vis[sx][sy][f[qx[0]=sx][qy[0]=sy][qz[0]=0]=0]=++dfn; for(int head=-1,tail=0;head!=tail;) { move(head); int frx=qx[head],fry=qy[head],frz=qz[head]; if(frx==sx&&fry==sy) getcmp(ans,f[frx][fry][frz],greater<int>()); REP(i,0,3) { int tox=frx+dx[i],toy=fry+dy[i]; if(tox&&toy&&tox<=n&&toy<=m&&!map[tox][toy]) { int toz=frz,det=0; if(i<2) { int x,y; toy>fry?(x=tox,y=toy):(x=frx,y=fry); PER(j,line[y].size()-1,0) { int dig=line[y][j]; if(bx[dig]>=x) break; int bin=1<<dig-1; det+=(toz&bin?-1:1)*val[dig],toz^=bin; } } if(vis[tox][toy][toz]!=dfn||f[frx][fry][frz]+det-1>f[tox][toy][toz]) { f[tox][toy][toz]=f[frx][fry][frz]+det-1,vis[tox][toy][toz]=dfn; if(!inq[tox][toy][toz]) move(tail),inq[qx[tail]=tox][qy[tail]=toy][qz[tail]=toz]=1; } } } inq[frx][fry][frz]=0; } } int main() { 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); REP(i,1,n) REP(j,1,m) { char ch=getchar(); for(;isspace(ch)||ch==' ';ch=getchar()); int num=ch-'0'; switch(ch) { case '0':break; case '#':map[i][j]=1; break; default:map[bx[num]=i][j]=1,line[j].push_back(num); } } 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); return printf("%d ",ans),0; }