JZOJ 6313. Maja

$Description$

给定一张$n\times m$的矩阵，第$i$行第$j$列的权值是$a_{i,j}$，现在要求从$(A,B)$出发，走$k$步回到原地，求最高权值和

数据范围：$n,m\le 10^2,k\le 10^9$

$Solution$

结论1：路径一定是走到某个点再返回【显然】
结论2：路径一定在某处循环
结论3：循环节长度为2

复杂度：$O(n^2{m}^2)$

$Code$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 110
using namespace std;int n,m,A,B;
long long f[2][N][N],a[N][N],ans,K,w[N][N];
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
signed main()
{freopen("maja.in","r",stdin);freopen("maja.out","w",stdout);memset(f,0xcf,sizeof(f));scanf("%d%d%d%d%lld",&n,&m,&A,&B,&K);for(register int i=1;i<=n;i++)for(register int j=1;j<=m;j++)scanf("%lld",a[i]+j);f[0][A][B]=0;K/=2;for(register int k=1;k<=min(1ll*n*m,K);k++){memset(f[k&1],0xcf,sizeof(f[k&1]));for(register int i=1;i<=n;i++)for(register int j=1;j<=m;j++){if(k==1){for(register int l=0;l<4;l++) w[i][j]=max(w[i][j],a[i+dx[l]][j+dy[l]]);w[i][j]+=a[i][j];}for(register int l=0;l<4;l++)f[k&1][i][j]=max(f[k&1][i][j],f[~k&1][i+dx[l]][j+dy[l]]+a[i][j]);if(f[k&1][i][j]<0) continue;ans=max(ans,(f[k&1][i][j]+(K-k)/2*w[i][j])*2-a[i][j]);}}printf("%lld",ans);
}