前缀和优化DP
F - Manhattan Cafe (atcoder.jp)
题意
给定 n，d（n <= 100, d <= 1000）
在 n 维空间中, 给定两个点 p，q，求点 r 的数量，满足 r 与 p，q 的曼哈顿距离均 <= d
思路
首先考虑朴素dp，设 \(f[k][i][j]\) 表示考虑前 k 维，r 与 p 的曼哈顿距离为 i，与 q 的曼哈顿距离为 j 的点的数量
对于第 k + 1 维，枚举 r 第 k + 1 维的坐标，进行转移
这样复杂度为 \(O(nd^3)\)
首先考虑优化空间，第一维可以滚动
再考虑优化转移复杂度，朴素的转移复杂度为 \(O(d)\), 但实际上不需要枚举第 k + 1 维每个坐标，这些坐标可以分成两类，记第 i 维 p，q，r 的坐标分别为 \(p_i,q_i,r_i\)
可以分为 \(r_i\) 在 $p_i,q_i $ 中间或两侧
设 \(z=|p-q|\)
- \(r_i\) 在中间
从 0 到 z 枚举 t，\(f[i][j]+=f[i-t][j-s]\), 因为 t + s == z, 为定值，因此所有的 \(f[i-t][j-s]\) 都在以 \(x+y=i+j-z\) 的副对角线上，用前缀和优化转移即可
- \(r_i\) 在两侧
同理，\(f[i][j]+=f[i-t][j-s]\), t - s 为定值 z，因此所有的 \(f[i-t][j-s]\) 都在 \(y-x=j-i+z\) 的主对角线上，前缀和优化转移即可
r 在 p 右边同理
每次算完当前的 \(f[i][j]\) 后，要更新两个对角线前缀和矩阵
总结
本题的关键是前缀和优化转移，但前缀和是对角线的形式，比较少见，而且考虑边界问题较多，出现负数时及时特判
优化转移时一定要画图！
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e3 + 10, M = 1e2 + 10, mod = 998244353;
int n, d;
int p[M], q[M];
ll f[N][N], C[2][N][N], E[2][N][N];
//C[i][j]表示以(i,j)为终点的主对角线的f的前缀和
//E[i][j]表示以(i,j)为终点的副对角线，从 右上 到 (i,j) 的f的前缀和
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> d;
for (int i = 1; i <= n; i++)
cin >> p[i];
for (int i = 1; i <= n; i++)
cin >> q[i];
for (int i = 0; i <= d; i++)
C[0][i][i] = 1;
E[0][0][0] = 1;
for (int k = 1; k <= n; k++)
{
int a = k & 1, b = a ^ 1;
int z = abs(p[k] - q[k]);
for (int i = 0; i <= d; i++)
{
for (int j = 0; j <= d; j++)
{
f[i][j] = 0;
//前缀和优化转移
//这里不能取到端点，因为端点在第二种情况被包括了
if (i - 1 >= 0 && j - z - 1 >= 0)
f[i][j] += C[b][i-1][j-z-1];
if (j - 1 >= 0 && i - z - 1 >= 0)
f[i][j] += C[b][i-z-1][j-1];
f[i][j] %= mod;
if (i + j >= z)
{
//找到合法的那一段对角线
int r = min(i, i + j - z), l = i + j - z - min(j, i + j - z) - 1;
f[i][j] += E[b][r][i+j-z-r];
if (l >= 0)
f[i][j] -= E[b][l][i+j-z-l];
f[i][j] = (f[i][j] % mod + mod) % mod;
}
//更新两个对角线前缀和矩阵
if (i >= 1 && j >= 1)
C[a][i][j] = (C[a][i-1][j-1] + f[i][j]) % mod;
else
C[a][i][j] = f[i][j];
if (i >= 1)
E[a][i][j] = (E[a][i-1][j+1] + f[i][j]) % mod;
else
E[a][i][j] = f[i][j];
}
}
}
ll ans = 0;
for (int i = 0; i <= d; i++)
for (int j = 0; j <= d; j++)
ans = (ans + f[i][j]) % mod;
cout << ans << endl;
return 0;
}