[ABC265F] Manhattan Cafe Solution

[ABC265F] Manhattan Cafe Solution更好的阅读体验戳此进入题面SolutionCodeUPD

更好的阅读体验戳此进入

题面

$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$ 则转移为：

d p (i, j, k) = \sum_{x} d p (i, j - | x - p_{i} |, k - | x - q_{i} |) \times [| x - p_{i} | \leq d \land | x - q_{i} | \leq 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$ ，即为：

d p (j, k) = s u m (j - d i s, k) - s u m (j - d i s, k - d i s - 1) + s u m_{2} (j - d i s - 2, k - 1) + s u m_{2} (j - d i s - 2, k - d i s - 1)

$p, q$ $p, q$ 的两侧。

$sum, sum_2$ 即可。

$O(nd^2)$ ，可以通过。

Code


xxxxxxxxxx
81
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, D;
28
int P[110], Q[110];
29
ll dp[2100][1100];
30
ll sum[2100][1100];
31
ll sum2[2100][1100];
32
ll ans(0);
33

34
int main(){
35
    N = read(), D = read();
36
    for(int i = 1; i <= N; ++i)P[i] = read();
37
    for(int i = 1; i <= N; ++i)Q[i] = read();
38
    dp[0][0] = 1;
39
    for(int j = 0; j <= D * 2; ++j)
40
        for(int k = 0; k <= D; ++k)
41
            sum[j][k] = ((k - 1 >= 0 ? sum[j][k - 1] : 0) + dp[j][k]) % MOD,
42
            sum2[j][k] = ((j - 2 >= 0 && k - 1 >= 0 ? sum2[j - 2][k - 1] : 0) + dp[j][k]) % MOD;
43
    for(int i = 1; i <= N; ++i){
44
        for(int j = 0; j <= D * 2; ++j)
45
            for(int k = 0; k <= D; ++k){
46
                int dis = abs(P[i] - Q[i]);
47
                dp[j][k] = j >= dis
48
                    ?
49
                        ((sum[j - dis][k] - (k - dis - 1 >= 0 ? sum[j - dis][k - dis - 1] : 0) + MOD) % MOD +
50
                        (j - dis - 2 >= 0 && k - 1 >= 0 ? sum2[j - dis - 2][k - 1] % MOD : 0) +
51
                        (j - dis - 2 >= 0 && k - dis - 1 >= 0 ? sum2[j - dis - 2][k - dis - 1] % MOD : 0)) % MOD
52
                    : 0;
53
            }
54
        memset(sum, 0, sizeof sum), memset(sum2, 0, sizeof sum2);
55
        for(int j = 0; j <= D * 2; ++j)
56
            for(int k = 0; k <= D; ++k)
57
                sum[j][k] = ((k - 1 >= 0 ? sum[j][k - 1] : 0) + dp[j][k]) % MOD,
58
                sum2[j][k] = ((j - 2 >= 0 && k - 1 >= 0 ? sum2[j - 2][k - 1] : 0) + dp[j][k]) % MOD;
59
    }
60
    for(int j = 0; j <= D * 2; ++j)for(int k = 0; k <= min(j, D); ++k)
61
        if(j - k <= D) (ans += dp[j][k]) %= MOD;
62
    printf("%lld\n", ans);
63
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
64
    return 0;
65
}
66

67
template < typename T >
68
inline T read(void){
69
    T ret(0);
70
    int flag(1);
71
    char c = getchar();
72
    while(c != '-' && !isdigit(c))c = getchar();
73
    if(c == '-')flag = -1, c = getchar();
74
    while(isdigit(c)){
75
        ret *= 10;
76
        ret += int(c - '0');
77
        c = getchar();
78
    }
79
    ret *= flag;
80
    return ret;
81
}

UPD

update-2023_01_05 初稿