题意
你要从\((0,0)\)走到\((n - 1, m - 1)\)（向右或向下），在某些时刻在某些点可能会出现一些障碍，并且这些障碍会按周期跳动：
\[(x, y) \rightarrow (x + d, y - d) \rightarrow (x + d, y) \rightarrow (x, y + d) \rightarrow (x, y) ...\]
其中\((x, y)\)是该障碍点出现的位置，\(d\)是每次跳动的参数。
每当遇到一个障碍要花费一定的代价消灭它，并且之后就不会出现了。
求要花费的最小代价。
\(n, m \leq 500\)，\(障碍数 \leq 500000\)。
题解
这个dp其实很奇怪。因为一个简单的dp并不能解决这道题，在第二次遇到同一个障碍时会产生多余的贡献。
为了方便，我们把每个障碍的周期性跳跃和\(0, 1, 2, 3\)建立一个映射：
\[(x, y) \rightarrow 0 \\(x + d, y - d) \rightarrow 1 \\(x + d, y) \rightarrow 2 \\(x, y + d) \rightarrow 3 \\\]
注意到，在某一个确定的时刻\(t\)，所在位置\((x, y)\)的\(x + y\)值是确定的。
这个性质很重要，这意味着不会存在遇到同一个障碍的\(<0, 1>\)状态，同样的状态对还有\(<2, 3>\)。
并且根据周期性跳跃路径的性质，遇到同一个状态最多两次。
考虑产生多余贡献的状态对可能是\(<0, 2>\)，\(<1, 2>\)， \(<0, 3>\)，并且还要障碍本身满足一定的条件。
为了将“出现时间不同”这个限制去掉，就要预处理哪些障碍有概率会遇到，还要预处理出哪些贡献有概率会被多计算。
这样，我们可以预处理出前缀和数组\(s[0 / 1][i][j]\)表示\((i, j)\)位置同一列上面的/同一行左边的可能出现的障碍的贡献之和。
考虑设\(dp_{i, j}\)表示到\((i, j)\)的最小代价。
同一行的转移：
\[dp_{i, j} = min\{dp_{i - k, j} + s_{1, i, j} - s_{1, i - k, j} - dlt\}\]
\(dlt\)就是重复计算的贡献。这种贡献只可能是\(<0, 2>\)这种状态对产生的。这个东西却比较难处理。
考虑这种状态对在点\((i - k, j)\)到点\((i, j)\)产生多余的贡献必须满足
\[(x, j) \rightarrow 0 \\(x + d, j) \rightarrow 2 \\x \geq i \and x + d \leq i + k\]
这个东西在动规的时候直接前缀和做一下就好了。
同一列的转移也类似。
具体细节还是很多的，具体处理详见代码。
时间复杂度\(\mathcal O(n ^ 3)\)，空间复杂度\(\mathcal O(n ^ 2)\)。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 505;
typedef pair <int, int> pii;
int n, m, k;
ll dp[N][N], sum[N][N], s[2][N][N], d[2][N][N];
vector <pii> c[2][N][N];
bool add (int x, int y, int t, int e) {
if (x + y - 2 >= t && t % 4 == (x + y - 2) % 4) {
return sum[x][y] += e, 1;
} else {
return 0;
}
}
int main () {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1, x, y, d, t, e; i <= k; ++i) {
scanf("%d%d%d%d%d", &x, &y, &d, &t, &e), ++x, ++y;
if (add(x, y, t, e)) {
if (d % 4 == 3) {
c[0][x][y + d].push_back(make_pair(d, e));
}
if (d % 4 == 2) {
c[1][x + d][y].push_back(make_pair(d, e));
}
}
if (add(x + d, y - d, t + 1, e)) {
if (d % 4 == 1) {
c[0][x + d][y].push_back(make_pair(d, e));
}
}
add(x + d, y, t + 2, e);
add(x, y + d, t + 3, e);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
s[0][i][j] = s[0][i][j - 1] + sum[i][j];
s[1][i][j] = s[1][i - 1][j] + sum[i][j];
}
}
for (int i = 1; i <= n; ++i) {
dp[i][0] = 1ll << 60;
}
for (int j = 1; j <= m; ++j) {
dp[0][j] = 1ll << 60;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i == 1 && j == 1) {
dp[i][j] = sum[i][j];
continue;
} else {
dp[i][j] = 1ll << 60;
}
for (pii p : c[0][i][j]) {
d[0][i][j - p.first] += p.second;
}
for (pii p : c[1][i][j]) {
d[1][i - p.first][j] += p.second;
}
ll vx = 0, vy = 0;
for (int k = 1; k < j; ++k) {
vx += d[0][i][j - k];
dp[i][j] = min(dp[i][j], dp[i][j - k] + s[0][i][j] - s[0][i][j - k] - vx);
}
for (int k = 1; k < i; ++k) {
vy += d[1][i - k][j];
dp[i][j] = min(dp[i][j], dp[i - k][j] + s[1][i][j] - s[1][i - k][j] - vy);
}
}
}
printf("%lld\n", dp[n][m]);
return 0;
}