1187: [HNOI2007]神奇游乐园 插頭dp

Description

給定n*m大小的格子，每個格子有自己的權值。求一條不重複經過的回路使得路徑上權值之和最大。

Solution

莫名其妙就只能打繁體了。。

看起來就像插頭dp。我們設f[i,j,S]表示到了i,j，輪廓綫狀態為S的最大價值。轉移的時候討論一下括號的方向就可以了

需要注意的是本題只要一個回路，且回路可以任意大小，那麽只要出現合并同一個連通分量的兩個括號就可以更新答案，并且不需要繼續往後推。

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (register int i=st;i<=ed;++i)
#define drp(i,st,ed) for (register int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))

const int INF=0x3f3f3f3f;
const int N=2190;
const int L=10;

int rc[105][8],bin[25],rec[N],rnk[2190],n,m,tot;
int f[105][8][N],ans=-INF;

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

inline int get(int S,int p) {
	return (S/bin[p])%3;
}

inline void dfs(int dep,int sum,int S) {
	if (sum<0||sum+dep-1>m) return ;
	if (dep>m) {
		rec[++tot]=S,rnk[S]=tot;
		return ;
	}
	dfs(dep+1,sum,S);
	dfs(dep+1,sum+1,S+bin[dep]);
	dfs(dep+1,sum-1,S+2*bin[dep]);
}

inline int left(int S,int i) {
	int sum=0;
	for (;~i;--i) {
		int x=get(S,i);
		if (x==1) --sum;
		else if (x==2) ++sum;
		if (!sum) return bin[i];
	}
	return -1;
}

inline int righ(int S,int i) {
	int sum=0;
	for (;i<=m;++i) {
		int x=get(S,i);
		if (x==1) ++sum;
		else if (x==2) --sum;
		if (!sum) return bin[i];
	}
	return -1;
}

void update(int &x,int v) {
	(x<v)?(x=v):0;
}

int main(void) {
	bin[0]=1; rep(i,1,15) bin[i]=bin[i-1]*3;
	scanf("%d%d",&n,&m);
	if (n<m) std:: swap(n,m);
	rep(i,1,n) rep(j,1,m) rc[i][j]=read();
	dfs(0,0,0);
	fill(f,-31);
	f[1][0][rnk[0]]=0;
	rep(i,1,n) {
		rep(j,1,m) rep(k,1,tot) {
			int S=rec[k],p=get(S,j-1),q=get(S,j);
			int tmp=f[i][j-1][k]+rc[i][j];
			if (!p&&!q) {
				update(f[i][j][rnk[S+bin[j-1]+2*bin[j]]],tmp);
				update(f[i][j][k],f[i][j-1][k]);
			}
			if (!p&&q) {
				update(f[i][j][k],tmp);
				update(f[i][j][rnk[S-q*(bin[j]-bin[j-1])]],tmp);
			}
			if (p&&!q) {
				update(f[i][j][k],tmp);
				update(f[i][j][rnk[S-p*(bin[j-1]-bin[j])]],tmp);
			}
			if (p==1&&q==1) update(f[i][j][rnk[S-bin[j-1]-bin[j]-righ(S,j)]],tmp);
			else if (p==2&&q==2) update(f[i][j][rnk[S-2*(bin[j-1]+bin[j])+left(S,j-1)]],tmp);
			else if (p==2&&q==1) update(f[i][j][rnk[S-2*bin[j-1]-bin[j]]],tmp);
			else if (p==1&&q==2&&S-p*bin[j-1]-q*bin[j]==0) update(ans,tmp);
		}
		if (i!=n) rep(k,1,tot) if (rec[k]%3==0) update(f[i+1][0][k],f[i][m][rnk[rec[k]/3]]);
	}
	printf("%d\n", ans);
	return 0;
}