题意
你要从((0,0))走到((n - 1, m - 1))（向右或向下），在某些时刻在某些点可能会出现一些障碍，并且这些障碍会按周期跳动：
其中((x, y))是该障碍点出现的位置，(d)是每次跳动的参数。
每当遇到一个障碍要花费一定的代价消灭它，并且之后就不会出现了。
求要花费的最小代价。
(n, m leq 500)，(障碍数 leq 500000)。
题解
这个dp其实很奇怪。因为一个简单的dp并不能解决这道题，在第二次遇到同一个障碍时会产生多余的贡献。
为了方便，我们把每个障碍的周期性跳跃和(0, 1, 2, 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))的最小代价。
同一行的转移：
(dlt)就是重复计算的贡献。这种贡献只可能是(<0, 2>)这种状态对产生的。这个东西却比较难处理。
考虑这种状态对在点((i - k, j))到点((i, j))产生多余的贡献必须满足
这个东西在动规的时候直接前缀和做一下就好了。
同一列的转移也类似。
具体细节还是很多的，具体处理详见代码。
时间复杂度(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
", dp[n][m]);
return 0;
}