[BZOJ1187]神奇游乐园（插头DP）

Description

题意给定一个矩阵，每个格子有权值，在[-1000.1000]内，求一条回路使得回路经过权值和最大，每个格子最多经过一次

2≤n≤100，2≤m≤6

Code

#include <cstdio>

#include <algorithm>

#define N 10

#define Inf 0x7fffffff

using namespace std;

int A[N],now,op[N],k[N],L[N],Ans=-Inf;

int n,m,g[110][N],dp[2][20000],q[2][20000],t[2];

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

void push(int x,int y){

	if(dp[now^1][x]==-Inf) q[now^1][++t[now^1]]=x;

	dp[now^1][x]=max(dp[now^1][x],y);

}

void clear(){

	for(int i=1;i<=t[now];++i) dp[now][q[now][i]]=-Inf;

	t[now]=0;

	now^=1;

}

void f(int S){

	int tp=0;

	for(int i=0;i<=m;++i){

		k[i]=S&3,S>>=2;//

		if(k[i]==1) L[++tp]=i;

		else if(k[i]==2) op[op[i]=L[tp--]]=i;

	}

}

void bfs(int x,int y){

	clear();

	for(int i=1;i<=t[now];++i){

		int S=q[now][i];

		f(S);

		int l=k[y-1],r=k[y],upd=dp[now][S]+g[x][y];

		if(!l&&!r){

			push(S,upd-g[x][y]);

			push(S+A[y-1]+(A[y]<<1),upd);

		}else if(l&&r){

			int tS=S-l*A[y-1]-r*A[y];

			if(l==2&&r==1) push(tS,upd);

			else if(l==1&&r==1) push(tS-A[op[y]],upd);

			else if(l==2&&r==2) push(tS+A[op[y-1]],upd);

			else if(!tS) Ans=max(Ans,upd);

		}

		else{

			push(S,upd);

			push(S-l*A[y-1]-r*A[y]+l*A[y]+r*A[y-1],upd);

		}

	}

}

int main(){

	A[0]=1;for(int i=1;i<N;++i)A[i]=A[i-1]<<2;//四进制

	for(int i=0;i<2;++i)for(int j=0;j<20000;++j)dp[i][j]=-Inf;

	n=read(),m=read();

	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)g[i][j]=read();

	push(0,0);

	for(int i=1;i<=n;++i){

		clear();

		for(int j=1;j<=t[now];++j) if(q[now][j]<A[m]) push(q[now][j]<<2,dp[now][q[now][j]]);

		for(int j=1;j<=m;++j) bfs(i,j);

	}

	printf("%d\n",Ans);

	return 0;

}