[training Day12] be go! [dynamic programming] [mathematics]

Ideas ：

We found that it must be walking to a point and back and forth between two points , So we set f[i][j] Said go i,j The path length of , And then transfer m*n Time （ You can walk to every point on the map ）, Then greedily choose the one with the largest weight among the adjacent points of each point and walk back and forth .

$code$

#include<iostream>
#include<cstdio>
 
#define re register
#define ll long long
 
using namespace std;

const ll MAXN = 110;
 
ll n, m, A, B, k, ans = -1e18;
ll f[MAXN][MAXN], g[MAXN][MAXN], a[MAXN][MAXN];
bool v[MAXN][MAXN], v1[MAXN][MAXN];

int main() {
    
// freopen("maja.in", "r", stdin);
// freopen("maja.out", "w", stdout);
	scanf("%lld%lld%lld%lld%lld", &n, &m, &A, &B, &k);
	for(re ll i = 1; i <= n; ++ i)
 		for(re ll j = 1; j <= m; ++ j)
 			scanf("%lld", &a[i][j]);
	for(re ll i = 0; i <= n + 1; i ++)
		for(re ll j = 0; j <= m + 1; j ++) g[i][j] = 0;
 	g[A][B] = 0, v1[A][B] = 1, v[A][B] = 1;
	for(re ll len = 1; len <= n * m; ++ len) {
    
 		if(len * 2 > k) break;
		for(re ll i = 1; i <= n; ++ i)
 			for(re ll j = 1; j <= m; ++ j) {
    
 				if(i > 1 && v1[i - 1][j] != 0) f[i][j] = g[i - 1][j] + a[i][j], v[i][j] = 1;
				if(i < n && v1[i + 1][j] != 0) f[i][j] = max(f[i][j], g[i + 1][j] + a[i][j]), v[i][j] = 1;
 				if(j > 1 && v1[i][j - 1] != 0) f[i][j] = max(f[i][j], g[i][j - 1] + a[i][j]), v[i][j] = 1;
				if(j < m && v1[i][j + 1] != 0) f[i][j] = max(f[i][j], g[i][j + 1] + a[i][j]), v[i][j] = 1;
 			}
		for(re ll i = 1; i <= n; ++ i) 
			for(re ll j = 1; j <= m; ++ j) {
    
				v1[i][j] = v[i][j] | v1[i][j];
				v[i][j] = v1[i][j];
				if(v[i][j] == 1) g[i][j] = f[i][j];
 				ll p = 0;
				p = max(a[i + 1][j], max(a[i - 1][j], max(a[i][j + 1], a[i][j - 1])));
				if(v[i][j] == 1) ans = max(ans, f[i][j] * 2 - a[i][j] * 1 + (k - len * 2) / 2 * (a[i][j] + p));
			}
   	}
	printf("%lld", ans);
	return 0;
}