【JZOJ6313】Maja【dp】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/6313
一个$n imes m$的网格图，经过点$(x,y)$可以获得$a_{x,y}$的价值，一个点可以 经过多次。求从$(x,y)$出发，走$p$步后回到$(x,y)$的最大价值。

---

思路：

这道题有三个相对显然的性质。

1. 最终一定是走过某些格子，然后原路返回到原点。
2. 为了最大化价值，人物如果产生循环节，那么必然是走到循环节，然后兜上几圈再原路返回。
3. 不难证明，这个循环节的大小为2。

其中性质$1,2$都十分显然。那么下面简单证明一下性质三。
orzWYCdalao的证明

假设这个循环节由$k(k>2)$个格子组成。那么取其中三个相邻的点$x,y,z$。
如果$z$的权值小于$x$的权值，那么显然在$x,y$中循环会优于在$x,y,z$中循环。
如果$z$的权值大于$x$的权值，那么显然在$y,z$中循环会优于在$x,y,z$中循环。
证毕。

利用循环节为2的性质，我们就设$f[k][i][j]$表示走了$k$步到达点$(i,j)$的最大价值。
那么$f[k][i][j]$可以从上下左右四个方向转移而来，所以
$f[k][i][j]=max(f[k][i][j],f[k-1][i+dx[l]][j+dy[l]]+a[i][j])$

但是这样空间不支持。
我们发现$f[k]$只和$f[k-1]$有关。所以滚动就可以了。
每次求出$f[k&1][i][j]$之后就更新$ans$。以$(x,y)$为中心的循环节可以预处理出来，反正就只有四种情况。
时间复杂度最坏$O(n^2m^2)$

---

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=110;
const ll Inf=1e18;
const int dx[]={0,0,0,-1,1},dy[]={0,1,-1,0,0};
ll ans,f[2][N][N],a[N][N],maxn[N][N];
int n,m,sx,sy,p;

int main()
{
	freopen("maja.in","r",stdin);
	freopen("maja.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&p);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%lld",&a[i][j]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			for (int k=1;k<=4;k++)
				maxn[i][j]=max(maxn[i][j],a[i][j]+a[i+dx[k]][j+dy[k]]);
	memset(f,0xcf,sizeof(f));
	f[0][sx][sy]=0;
	for (int k=1;k<=min(p/2,n*m);k++)
	{
		memset(f[k&1],0xcf,sizeof(f[k&1]));
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				for (int l=1;l<=4;l++)
					f[k&1][i][j]=max(f[k&1][i][j],f[(k+1)&1][i+dx[l]][j+dy[l]]+a[i][j]);
				if (f[k&1][i][j]<0) f[k&1][i][j]=-Inf;
					else ans=max(ans,f[k&1][i][j]*2+(ll)(p/2-k)*maxn[i][j]-a[i][j]);
			}
	}
	printf("%lld",ans);
	return 0;
}