Luogu-P9743-旅行

Posted on Edited on Word count in article: 2k

题目 P9743 「KDOI-06-J」旅行

题目描述

小 C 在 C 国旅行。

C 国有 $n\times m$ 个城市，可以看做 $n\times m$ 的网格。定义 $(i,j)$ 表示在网格中第 $i$ 行第 $j$ 列的城市。

该国有 $2$ 种交通系统：

  • 对于所有 $1\leq i<n,1\leq j\leq m$，$(i,j)$ 到 $(i+1,j)$ 有一段由 L 公司修的单向铁路；
  • 对于所有 $1\leq i\leq n,1\leq j<m$，$(i,j)$ 到 $(i,j+1)$ 有一段由 Z 公司修的单向铁路；

在每一个城市有一个售票口，$(i,j)$ 城市的售票口可以用 $a_{i,j}$ 元购买一张 L 公司的铁路票，$b_{i,j}$ 元购买一张 Z 公司的铁路票。当你拥有一个公司的一张铁路票时，你可以乘坐这个公司的任意一段铁路，并消耗掉这张铁路票。注意，一张铁路票可以且仅可以使用一次。

小 C 原来在城市 $(1,1)$。他想要在 C 国旅游，但是他不想浪费任何的钱（即，当他旅游完毕时手上不应该有多余的车票）。对于所有 $1\leq x\leq n,1\leq y\leq m$，求他花 $k$ 元钱并在城市 $(x,y)$ 结束旅行的方案数，对 $998\ 244\ 353$ 取模。

两种旅行方案不同，当且仅当小 C 经过的城市不同，或他在某一个城市购买的某家公司的铁路票数量不同。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n,m,k$，表示网格的大小和钱的数目。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $a_{i,j}$。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $b_{i,j}$。

输出格式

输出到标准输出。

输出一共 $n$ 行，每行 $m$ 个整数，表示到每个点钱恰好花完并结束旅行的方案数，对 $998\ 244\ 353$ 取模。

思路：dp

dp表

注意到本题对于一格共有 $5$ 个变量：

  • 横坐标 $x$
  • 纵坐标 $y$
  • 横着走的车票数 $sx$
  • 竖着走的车票数 $sy$
  • 剩余钱数 $money$

并且根据本题的数据范围，考虑五维的dp表 $dp[x][y][sx][sy][money]$。

状态

  • 初状态：由于初始位置是 $(1,1)$，此时两种车票都没有，剩余钱数为题中的 $k$，因此以下方程恒成立。

    1
    dp[1][1][0][0][k] = 1;

  • 状态转移方程：$dp[x][y][sx][sy][money]$ 为所有能变化成这种状态的方案数总和。

    而根据题意，存在以下状态可以变成 $dp[x][y][sx][sy][money]$：

    • 从 $(x-1, y)$，花费一张横向车票。$\rightarrow dp[x-1][y][sx+1][sy][money]$
    • 从 $(x, y-1)$，花费一张纵向车票。$\rightarrow dp[x][y-1][sx][sy+1][money]$
    • 原地花 $a[x][y]$ 的钱买一张横向车票。$\rightarrow dp[x][y][sx-1][sy][money+a[x][y]]$
    • 原地花 $b[x][y]$ 的钱买一张纵向车票。$\rightarrow dp[x][y][sx][sy-1][money+b[x][y]]$

    因此，$dp[x][y][sx][sy][money]$ 应为以上四个式子的和（注意取模）。

    1
    2
    3
    4
    5
    dp[x][y][sx][sy][money] += 
    dp[x - 1][y][sx + 1][sy][money] +
    dp[x][y - 1][sx][sy + 1][money] + 
    dp[x][y][sx - 1][sy][money + a[x][y]] + 
    dp[x][y][sx][sy - 1][money + b[x][y]];

    需要注意，以上方程并不正确。

    因为根据题意，购买车票的顺序不同是不算方案不同的，例：先买 $1$ 横向再买 $1$ 纵向，和先买 $1$ 纵向再买 $1$ 横向不应算两种方案。

    因此，还应该在同时买两种车票（$sx \neq 0 $且$ sy \neq 0$）时，去除重复部分 $dp[i][y][sx-1][sy-1][money+a[x][y]+b[x][y]]$。

  • 末状态：题目要求到达的点不能有票（$sx=sy=0$）和剩下的钱（$money=0$），因此到达 $(x,y)$ 的方案数为：

    1
    dp[x][y][0][0][0];

遍历的范围

  • $x$ 和 $y$ 自然是 $[1,n]$ 和 $[1,m]$
  • $sx$ 可以这样考虑：当横坐标为 $x$ 时，最多可拥有 $n-x$ 张横向的票，因为再多也用不上了。
    所以 $sx$ 的范围是 $[0,n-x]$。$sy$ 同理：$[0,m-y]$。
  • $money$ 比较特殊。虽然范围很容易想到是 $[0,k]$，但是方程中是由较大的钱数计算较小的钱数，所以要倒序循环。

空间压缩：滚动数组

此时，虽然看起来十分完美，但是数组太大了，会MLE。

注意到：当横坐标为 $x$ 时的方案数只与 $x$ 和 $x-1$ 有关，所以使用滚动数组方法将第一维压缩成 $2$ 而不是 $n$。

方法

使用一个变量 $i$ 存储 $x$的奇偶，每次循环将 $i$ 置为 $1 \ \mathrm{xor}\ i$。

压缩后状态

  • 初状态不变。

  • 状态转移方程中所有的 $x$ 换成 $i$，$x-1$ 换成 $1 \ \mathrm{xor} \ i$（另一个数组就是上一个 $x$）。

  • 末状态的处理有一些变化。因为 $dp$ 数组不再存储每个 $(x,y)$ 的方案数，所以应在计算完之后存到另一个数组 $ans$ 里。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// template v4
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int inf = 0x7fffffff;

const int N = 50;
const int M = 100;

int dp[2][N][M][M][M];

int A[N][N];
int B[N][N];

int ans[N][N];

const int MOD = 998244353;

int main() {

    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> A[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> B[i][j];
        }
    }
    dp[1][1][0][0][k] = 1;
    int i = 0;
    for(int x = 1; x <= n; x++){
        i ^= 1;
        for(int y = 1; y <= m; y++){
            for(int money = k; money >= 0; money--){
                for(int sx = 0; sx + x <= n; sx++){
                    for(int sy = 0; sy + y <= m; sy++){
                        ll res = 0;
                        if(x != 1) res += dp[i ^ 1][y][sx + 1][sy][money];
                        if(y != 1) res += dp[i][y - 1][sx][sy + 1][money];
                        res %= MOD;
                        if(sx && A[x][y] + money <= k) res += dp[i][y][sx - 1][sy][money+A[x][y]];
                        if(sy && B[x][y] + money <= k) res += dp[i][y][sx][sy - 1][money+B[x][y]];
                        if(sx && sy && A[x][y] + B[x][y] + money <= k) res += MOD - dp[i][y][sx - 1][sy - 1][money + A[x][y] + B[x][y]];
                        dp[i][y][sx][sy][money] += (res % MOD);
                        dp[i][y][sx][sy][money] %= MOD;
                    }
                }
            }
            ans[x][y] = dp[i][y][0][0][0];
        }
        memset(dp[i ^ 1], 0, sizeof dp[i ^ 1]);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}