题目描述
小 C 在 C 国旅行。
C 国有 n×m 个城市，可以看做 n×m 的网格。定义 (i,j) 表示在网格中第 i 行第 j 列的城市。
该国有 2 种交通系统：
- 对于所有 1≤i<n,1≤j≤m，(i,j) 到 (i+1,j) 有一段由 L 公司修的单向铁路；
- 对于所有 1≤i≤n,1≤j<m，(i,j) 到 (i,j+1) 有一段由 Z 公司修的单向铁路；
在每一个城市有一个售票口，(i,j) 城市的售票口可以用 ai,j 元购买一张 L 公司的铁路票，bi,j 元购买一张 Z 公司的铁路票。当你拥有一个公司的一张铁路票时，你可以乘坐这个公司的任意一段铁路，并消耗掉这张铁路票。注意，一张铁路票可以且仅可以使用一次。
小 C 原来在城市 (1,1)。他想要在 C 国旅游，但是他不想浪费任何的钱（即，当他旅游完毕时手上不应该有多余的车票）。对于所有 1≤x≤n,1≤y≤m，求他花 k 元钱并在城市 (x,y) 结束旅行的方案数，对 998 244 353 取模。
两种旅行方案不同，当且仅当小 C 经过的城市不同，或他在某一个城市购买的某家公司的铁路票数量不同。
输入格式
从标准输入读入数据。
输入的第一行包含三个正整数 n,m,k，表示网格的大小和钱的数目。
接下来 n 行，每行 m 个正整数，第 i 行第 j 个正整数表示 ai,j。
接下来 n 行，每行 m 个正整数，第 i 行第 j 个正整数表示 bi,j。
输出格式
输出到标准输出。
输出一共 n 行，每行 m 个整数，表示到每个点钱恰好花完并结束旅行的方案数，对 998 244 353 取模。
思路：dp
dp表
注意到本题对于一格共有 5 个变量：
- 横坐标 x
- 纵坐标 y
- 横着走的车票数 sx
- 竖着走的车票数 sy
- 剩余钱数 money
并且根据本题的数据范围，考虑五维的dp表 dp[x][y][sx][sy][money]。
状态
-
初状态：由于初始位置是 (1,1)，此时两种车票都没有，剩余钱数为题中的 k，因此以下方程恒成立。
-
状态转移方程：dp[x][y][sx][sy][money] 为所有能变化成这种状态的方案数总和。
而根据题意，存在以下状态可以变成 dp[x][y][sx][sy][money]：
- 从 (x−1,y)，花费一张横向车票。→dp[x−1][y][sx+1][sy][money]
- 从 (x,y−1)，花费一张纵向车票。→dp[x][y−1][sx][sy+1][money]
- 原地花 a[x][y] 的钱买一张横向车票。→dp[x][y][sx−1][sy][money+a[x][y]]
- 原地花 b[x][y] 的钱买一张纵向车票。→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=0,sy=0）时，去除重复部分 dp[i][y][sx−1][sy−1][money+a[x][y]+b[x][y]]。
-
末状态：题目要求到达的点不能有票（sx=sy=0）和剩下的钱（money=0），因此到达 (x,y) 的方案数为：
遍历的范围
-
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 xor i。
压缩后状态
-
初状态不变。
-
状态转移方程中所有的 x 换成 i，x−1 换成 1 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
|
#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;
}
|