Maja

题目

题目描述
$Maja$和蜜蜂在一片神奇的草地上为花授粉，这块草地可以表示为一个$n(n\le 100)$行$m(m\le 100)$列的矩形，在第$i$行第$j$列中有$C_{ij}(C_{ij}\le 1000000000)$朵没有授粉的花。

$Maja$的蜂巢位于第$a(1\le a\le n)$行第$b(1\le b\le n)$列，她将从她的蜂巢开始为这些花授粉，去草地上的某些块授粉，然后再返回她的蜂巢。每次操作，$Maja$可以向相邻的上下左右中的一个方格移动，而且她永远不会离开草地。每次她经过的某块草地，都会给这块草地上所有未授粉的花授粉。但草地很神奇，一旦$Maja$离开草地$(i,j)$，所有授粉的花都会消失，新的未授粉的花又会在这片土地上生长。

由于$Maja$不可能永远飞行，她会在飞过$k(2\le k\le 1000000000)$个格子后感到疲倦，并乐意向她的蜜蜂朋友们讲述她的冒险故事。请问，在$Maja$授粉并在$k$步后返回蜂巢，她能授粉的花的数量是多少？

输出输出格式
我不想打 见标程

思路

要是你不认真想正解 也能想到就算我输 ，你可以想到一个$BFS($或者$dp)$的做法——存一个位置$+$步数的状态。没错，它是$O(nmk)$的！相当的快呢！

好，接下来想正解：

• 起点和终点重合的路径，一定是“原路返回”！

为什么呢？因为走到 一半（没错就是恰好一半，毕竟你要走偶数步）的时候，你有两种选择：一：原路返回；二：接着走。你来的时候走哪条，哪条路的权值就大，回去的时候就该走哪条路。

• 路径中最多只会在两个点之间来回移动！

为什么呢？因为在$x(x>2)$个点（设为$p_1,p_2,p_3,...,p_x$）之间来回移动，等同于从$p_1$出发走一步（走到$p_2$）回来$+$从$p_2$出发走一步（走到$p_3$）回来$+...+$从$p_{x-1}$出发走一步回来。倒不如直接找$p_1,p_2,p_3,...,p_{x-1}$中出发走一步回来的值最大的一个，不断的这么走呢。

现在，凭借上面的结论，你已经知道路径长什么样子了：
后面那个黑坨坨表示反反复复 老不好，快用……

为什么不是中间的某一个区间反反复复，必须是头头上反反复复呢？

因为从中间反反复复，就会违背第一个结论了！

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;const int MAXN = 100,dis[][2] = {1,0,0,1,-1,0,0,-1};
const long long longInf = (1ll<<62)-1;
long long dp[2][MAXN][MAXN];// dp[s,x,y] 走2s步走到(x,y)最大的权值 
// s进行滚动，权值忽略反反复复 
int a[MAXN][MAXN];int main(){int n, m, k, x, y;scanf("%d %d %d %d %d",&n,&m,&x,&y,&k); k >>= 1;for(int i=0; i<n; ++i) for(int j=0; j<m; ++j)scanf("%d",&a[i][j]);for(int i=0; i<n; ++i) for(int j=0; j<m; ++j)dp[0][i][j] = -longInf;dp[0][x-1][y-1] = 0;long long ans=0;for(int step=1; step<=k and step<n*m; ++step){for(int i=0; i<n; ++i) for(int j=0; j<m; ++j){long long tmp = -longInf, d = -longInf;for(int dir=0,tox,toy; dir<4; ++dir){tox = i+dis[dir][0]; toy = j+dis[dir][1];if(tox < 0 or tox == n or toy < 0 or toy == m)continue;tmp = max(tmp,dp[(step&1)^1][tox][toy]+a[tox][toy]);
// 走到了(tox,toy)然后又走了一步走到(i,j)；a[i][j]在最后加 d = max(d,0ll+a[tox][toy]);
// 考虑最后反反复复的地方，肯定是a[i][j]+a[tox][toy] 
// 同样的，d中的a[i][j]也是最后加 }dp[step&1][i][j] = tmp+a[i][j];if(dp[step&1][i][j] < 0) continue; // 是-longInf ans = max(ans,dp[step&1][i][j]+(k-step)*(d+a[i][j]));}}printf("%lld",ans);return 0;
}