6313. Maja

Description

蜜蜂 Maja 到了一片草地，草地可以被描述成 N 行 M 列的网格图，在第 i 行第 j 列的位置上有 C_{i,j} 朵未授粉的花。
Maja 会从第 A 行第 B 列出发，每次只能移动到与当前位置四相邻的格子上，且不能移动到草地以外。每到达一个格子，她会把此处所有未授粉的花都授粉。
然而，当 Maja 离开一个格子，此处又会长出 C_{i,j} 朵未授粉的花。
Maja 想知道，如果她从第 A 行第 B 列出发，选择一条长度恰好为 K 的路径，最后又回到第 A 行第 B 列，最多能为多少朵花授粉。

Input

第一行 5 个正整数 N,M,A,B,K，如题面所述（K 一定是偶数）。
接下来 N 行每行 M 个非负整数，第 i 行第 j 个表示题面所述的 C_{i,j}。
数据保证 C_{A,B}=0。

Output

一个整数，表示授粉数的最大值。

Sample Input

Sample 1:
2 2 1 1 2
0 1
2 10Sample 2:
2 2 1 1 4
0 5
5 10Sample 3:
3 3 2 2 6
5 1 0
1 0 3
1 3 3

Sample Output

Sample 1:
2Sample 2:
20Sample 3:
15

Data Constraint

Solution

先考虑一个容易发现的性质：答案一定是先走到某个点，然后来回重复走某一条路径， 最后原路返回。

对于中间重复走的路径，可以证明它的大小为 2：如果大于 2，那么假设来回走一遍路 径上所有点，点权和的平均值为 x，必然存在一条长度小于它且大于等于 2 的路径，上 述平均值大于等于 x。例如 8-5-7，来回走一遍点权和为 5+8+5+7=25，平均值为 6.25， 此时选取 8-5，来回走一遍点权和为 8+5=13，平均值为 6.5

那么可以考虑 dp：设 f[k][i][j]表示从出发点走 k 步到了(i,j)的最大点权和，然后假 设第 k 步进入重复的路径，让他走到 (i,j)四相邻的点中点权最大的一个，然后计算答 案更新全局最大值即可。Dp 第一维只需设到 min(n*m,k/2)

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define rt return
#define P(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define N 103
using namespace std;
void rd(ll &x){x=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
ll a[N][N],p,n,m,A,B,K,x,y,fx[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
ll f[2][N][N],g[N][N],ans;
ll max(ll x,ll y){return x>y?x:y;}
I main(){P("maja");rd(n),rd(m),rd(A),rd(B),rd(K);F(i,1,n){F(j,1,m) rd(a[i][j]);}mem(f,-0x3f3f3f);f[0][A][B]=0;F(i,1,n){F(j,1,m){F(k,0,3){x=i+fx[k][0],y=j+fx[k][1];if(!x||!y||x>n||y>m) continue;g[i][j]=max(g[i][j],a[x][y]);	}g[i][j]+=a[i][j];}}p=0;F(k,1,min(n*m,K/2)){p=1-p;F(i,1,n){F(j,1,m){if(abs(A-i)+abs(B-j)>k) continue;F(l,0,3){x=i+fx[l][0],y=j+fx[l][1];if(!x||!y||x>n||y>m) continue;if(f[1-p][x][y]>=0) f[p][i][j]=max(f[p][i][j],f[1-p][x][y]+a[i][j]);}ans=max(ans,f[p][i][j]*2-a[i][j]+g[i][j]*(K/2-k));}}}printf("%lld\n",ans);rt 0;
}

作者：zsjzliziyang 
QQ:1634151125 
转载及修改请注明 
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/100016759