[ABC265F] Manhattan Cafe Solution
目录更好的阅读体验戳此进入
题面
在 $ n $ 维空间中存在 $ p, q $ 两点，求有多少个整点满足到 $ p, q $ 的曼哈顿距离均不大于 $ d $。
Solution
细节巨多的 DP。
首先有一个较为显然的 $ \texttt{3D1D} $ 的 $ O(nd^3) $ 的做法，即令 $ dp(i, j, k) $ 表示考虑前 $ i $ 维到 $ p $ 曼哈顿距离为 $ j $，到 $ q $ 曼哈顿距离为 $ k $ 的方案数，然后这个东西 $ O(d) $ 的转移较为显然，即枚举 $ i $ 维的坐标，令其为 $ x $ 则转移为：
\[dp(i, j, k) = \sum_x dp(i, j - \lvert x - p_i \rvert, k - \lvert x - q_i \rvert) \times [\lvert x - p_i \rvert \le d \land \lvert x - q_i \rvert \le d] \]然后这个东西实际上是可以通过类似前缀和的东西转移的，但是是类似对角线前缀和的，比较复杂细节巨多，所以这里参考以下机房大佬 @sssmzy 的做法。
考虑将状态修改为 $ dp(i, j, k) $ 表示考虑前 $ i $ 维，到 $ p $ 和 $ q $ 的曼哈顿距离和为 $ j $，到 $ p $ 的曼哈顿距离为 $ k $。
这个时候考虑两种可能性，对于某次枚举的位置 $ x $，若满足 $ p_i \le x \le q_i \lor q_i \le x \le p_i $，也就是说 $ x $ 在 $ p, q $ 之间，那么 $ j $ 这一维是从 $ j - \lvert p_i - q_i \rvert $ 转移而来，而 $ k $ 从 $ k $ 到 $ k - \lvert p_i - q_i \rvert $ 这段区间转移而来，那么即可以用前缀和转移。
考虑对于 $ x $ 在 $ p, q $ 之外的情况，那么对于每个 $ x \leftarrow x + 1 \lor x \leftarrow x - 1 $，显然存在 $ j \leftarrow j + 2, k \leftarrow j + 1 $。所以我们只需要再维护一个前缀和 $ sum_2(j, k) = sum_2(j - 2, k - 1) + dp(j, k) $ 即可。
具体来说，维护一个 $ sum $ 和 $ sum_2 $，意义同上。同时因为空间问题我们需要把第一维滚动掉。具体的转移即若 $ j \lt \lvert p_i - q_i \rvert $ 那么 $ dp(j, k) = 0 $。否则令 $ dis = \lvert p_i - q_i \rvert $，即为：
\[dp(j, k) = sum(j - dis, k) - sum(j - dis, k - dis - 1) + sum_2(j - dis - 2, k - 1) + sum_2(j - dis - 2, k - dis - 1) \]转移的意义即为在 $ p, q $ 中间和分别在 $ p, q $ 的两侧。
于是每次处理完 DP 后清空并重新维护 $ sum, sum_2 $ 即可。
最终复杂度为 $ O(nd^2) $，可以通过。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (998244353ll)
template < typename T = int >
inline T read(void);
int N, D;
int P[110], Q[110];
ll dp[2100][1100];
ll sum[2100][1100];
ll sum2[2100][1100];
ll ans(0);
int main(){
N = read(), D = read();
for(int i = 1; i <= N; ++i)P[i] = read();
for(int i = 1; i <= N; ++i)Q[i] = read();
dp[0][0] = 1;
for(int j = 0; j <= D * 2; ++j)
for(int k = 0; k <= D; ++k)
sum[j][k] = ((k - 1 >= 0 ? sum[j][k - 1] : 0) + dp[j][k]) % MOD,
sum2[j][k] = ((j - 2 >= 0 && k - 1 >= 0 ? sum2[j - 2][k - 1] : 0) + dp[j][k]) % MOD;
for(int i = 1; i <= N; ++i){
for(int j = 0; j <= D * 2; ++j)
for(int k = 0; k <= D; ++k){
int dis = abs(P[i] - Q[i]);
dp[j][k] = j >= dis
?
((sum[j - dis][k] - (k - dis - 1 >= 0 ? sum[j - dis][k - dis - 1] : 0) + MOD) % MOD +
(j - dis - 2 >= 0 && k - 1 >= 0 ? sum2[j - dis - 2][k - 1] % MOD : 0) +
(j - dis - 2 >= 0 && k - dis - 1 >= 0 ? sum2[j - dis - 2][k - dis - 1] % MOD : 0)) % MOD
: 0;
}
memset(sum, 0, sizeof sum), memset(sum2, 0, sizeof sum2);
for(int j = 0; j <= D * 2; ++j)
for(int k = 0; k <= D; ++k)
sum[j][k] = ((k - 1 >= 0 ? sum[j][k - 1] : 0) + dp[j][k]) % MOD,
sum2[j][k] = ((j - 2 >= 0 && k - 1 >= 0 ? sum2[j - 2][k - 1] : 0) + dp[j][k]) % MOD;
}
for(int j = 0; j <= D * 2; ++j)for(int k = 0; k <= min(j, D); ++k)
if(j - k <= D) (ans += dp[j][k]) %= MOD;
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2023_01_05 初稿
标签：int,题解,sum,sum2,MOD,Cafe,Manhattan,dp,dis From： https://www.cnblogs.com/tsawke/p/17032815.html