P2566 [SCOI2009]围豆豆

你的 DP，又何必是 DP？

本题是一个细节较多的 DP。

DP 的状态设置和大家的差不多，设 $f_{S,x,y}$ 表示包含状态为 $S$ 的所有节点，现在走到了 $(x,y)$ 格点。

至于 $S$ 的处理我是记录了每个豆子向上的射线穿过走过的路径次数的奇偶性，具体的处理其它题解已经说明，不再赘述。

但是在这篇题解里面介绍一种神奇的 DP 框架，很方便输出路径、维护最优解个数，以及维护 $k$ 优解等等。

它就是我们熟悉的老伙伴：DAG 上面的 DP。

DAG 有许多优秀的性质，比如求出拓扑序，在拓扑序上面即可线性地做 DP。

同时，因为压缩成为了图，所以只需要维护一个一维的 DP 数组，在其所有转移点的答案根据转移边取最大值即可。

我们在利用拓扑排序做 DP 的时候往往需要根据状态转移方程建点、建边。

算法特性：

• 时间空间都是 $O(n+m)$ 的，即状态加转移数。
• 需要状态对图中节点编号一一映射（有些时候还需双射）。
• 可以先拓扑排序，然后就顺序/倒序做，问题就变成了线性。

算法的好处：

• 无需确定枚举顺序。
• 只需要编码每个状态及其转移状态，对于初始值和最终答案适当设置起点终点即可。
• 换而言之，我们不需要考虑转移漏的问题了。
• 主要去计算的过程全程交给拓扑序上面的 DP。按照以往经验，这种 DP 非常简单。
• 对于输出最优解的方案数，只需要在原图上保留每个点的最优决策边，从起点到终点数路径数量即可。对于输出（最优字典序）路径，是同理的。
• 对于输出前 $k$ 优解，可以对于每个节点维护一个至多大小为 $k$ 的堆，这样编码十分简易。

不足之处：

• 需要维护每个状态对节点编号的双射，这就导致了编码的一些不便。
• 空间吃紧就不能用了。
• 增加了一定码量，如果碰到比较简洁的 DP 甚至不如直接用数组维护得方便易懂。
• 对于一些特殊图形（比如 1d/1d 动态规划的时候）不如使用其他特殊结构。
• 对于图分层的情况，无法使用滚动数组优化 DP。

这样的算法框架还是要结合具体题目具体分析，适当时候采用，可以优化自己的代码，以及减少码量。

这道题目天生就支持使用 bfs 框架拓展，所以我们把每个状态视为一个节点，把状态转移视为有向边。

在本题之中我们把每个状态 $(S,x,y)$ 再次压缩成为一个数字，变为节点编号。

首先枚举状态和状态转移方程，这里的状态可以随便枚举，反正是建边。

for(I i=n-1;~i;--i)
	for(I j=m-1,T;~j;--j)
		if(a[i][j]=='0')
			for(I di=3;~di;--di){
				I x=i+dx[di],y=j+dy[di];
				if(0<=x&&x<n&&0<=y&&y<m&&a[x][y]=='0'){
					T=0;
					for(I k=n,ay;k;--k){
						ay=ps[k].second;
						if(((j==ay&&y==ay+1)||(y==ay&&j==ay+1))&&x<ps[k].first)
							T^=(1<<k-1);}
					for(I S=(1<<d)-1;~S;--S)
						conn(id(S,i,j),id(S^T,x,y));}}

然后枚举起点终点进行 DP。

碰到这里大家可能会写一个很长的 BFS，但是这里的 bfs 只有寥寥几行：

I calc(I x,I y){
	I ans=-inf,st;
	for(I i=n*m*(1<<d);~i;--i)dis[i]=inf;
	dis[st=id(0,x,y)]=0;
	for(q[ql=qr=1]=st;ql<=qr;++ql){
		I x=q[ql];
		for(auto y:e[x]){
			if(dis[y]!=inf)continue;
			dis[y]=dis[x]+1;
			fr[y]=x;
			q[++qr]=y;}}
	for(I S=(1<<d)-1;~S;--S){
		ans=max(ans,anrs[S]-dis[id(S,x,y)]);}
	return ans;}

简不简单！因为把整个 DP 的所有状态浓缩到了这些节点里面，把所有状态转移方程浓缩到了边里面。

按照边无脑转移即可。

所以就写出了本题不是很长的代码：

#include<bits/stdc++.h>
using namespace std;typedef int I;typedef long long LL;const I inf=0x3f3f3f3f;
#define mp make_pair
const I N=11,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
I n,m,d;
char a[N][N];
I v[N],anrs[513];
pair<I,I>ps[N];
I id(I S,I x,I y){
	return S*n*m+x*m+y;}
const I SN=51210;
vector<I>e[SN];
void conn(I x,I y){e[x].push_back(y);}
I dis[SN],q[SN],ql,qr,fr[SN];
I calc(I x,I y){
	I ans=-inf,st;
	for(I i=n*m*(1<<d);~i;--i)dis[i]=inf;
	dis[st=id(0,x,y)]=0;
	for(q[ql=qr=1]=st;ql<=qr;++ql){
		I x=q[ql];
		for(auto y:e[x]){
			if(dis[y]!=inf)continue;
			dis[y]=dis[x]+1;
			fr[y]=x;
			q[++qr]=y;}}
	for(I S=(1<<d)-1;~S;--S){
		ans=max(ans,anrs[S]-dis[id(S,x,y)]);}
	return ans;}
I main(){
	scanf("%d%d%d",&n,&m,&d);
	for(I i=1;i<=d;++i)scanf("%d",v+i);
	for(I S=(1<<d)-1;~S;--S){
		for(I i=1;i<=d;++i)if(S&(1<<i-1))anrs[S]+=v[i];}
	for(I i=0;i<n;++i){
		scanf("%s",a[i]);
		for(I j=0;j<m;++j){
			if('1'<=a[i][j]	&& a[i][j]<='9')
				ps[a[i][j]-'0']=mp(i,j);}}
	for(I i=n-1;~i;--i)
		for(I j=m-1,T;~j;--j)
			if(a[i][j]=='0')
				for(I di=3;~di;--di){
					I x=i+dx[di],y=j+dy[di];
					if(0<=x&&x<n&&0<=y&&y<m&&a[x][y]=='0'){
						T=0;
						for(I k=n,ay;k;--k){
							ay=ps[k].second;
							if(((j==ay&&y==ay+1)||(y==ay&&j==ay+1))&&x<ps[k].first)
								T^=(1<<k-1);}
						for(I S=(1<<d)-1;~S;--S)
							conn(id(S,i,j),id(S^T,x,y));}}
	I ans=-inf;
	for(I i=n-1;~i;--i)
		for(I j=m-1;~j;--j)
			if(a[i][j]=='0')
				ans=max(calc(i,j),ans);
	printf("%d\n",ans);
	return 0;
}

以后可能还有这种状态很复杂的 DP，编码和调试都是一件难事，但是这种方法还是能够稍稍简化调试的复杂度的。

只需要调试状态转移方程即可。