题解：P9743 「KDOI-06-J」旅行
Eddie08012025
·
·
题解
基本思路
首先，看到此题数据范围 n,m\le 45,k\le 90 很小，可以想到做一个高复杂度的 dp。
考虑如何转移，转移方程大概可以分成两个部分：
1. 在格子 $(i,j)$ 购买车票，购买一张 L 公司的铁路票花费 $a_{i,j}$ 元，购买一张 Z 公司的铁路票花费 $b_{i,j}$ 元。得：
$$dp_{i,j,x+1,y,u-a_{i,j}}+=dp_{i,j,x,y,u}$$
$$dp_{i,j,x,y+1,u-b_{i,j}}+=dp_{i,j,x,y,u}$$
2. 在格子 $(i,j)$ 花费一张车票乘坐铁路，乘坐 L 公司的铁路会从 $(i,j)$ 到达 $(i+1,j)$ 并花费一张 Z 公司的铁路票，乘坐 Z 公司的铁路会从 $(i,j)$ 到达 $(i,j+1)$ 并花费一张 Z 公司的铁路票。得：
$$dp_{i+1,j,x-1,y,u}+=dp_{i,j,x,y,u}(i<n)$$
$$dp_{i,j+1,x,y-1,u}+=dp_{i,j,x,y,u}(j<m)$$
如果你不加任何优化直接 dp，你将会得到 $70$ 分的 MLE 与 TLE。现在考虑优化。
## 优化 DP
### 优化空间
发现 $dp_i$ 只会影响到 $dp_{i+1}$，所以可以用滚动数组优化。将分数优化到 $85$ 分 TLE。
### 优化时间
发现在 $(i,j)$ 时最多还会用到 $n-i$ 张 L 公司的票与 $m-j$ 张 Z 公司的票，买多了票对答案不会有贡献，因此我们在循环枚举 $x,y$ 时可以加上条件 $x\le n-i$ 与 $y\le m-j$。在购买车票时会花费钱 $a_{i,j}$ 或 $b_{i,j}$，$u\le a_{i,j},b_{i,j}$ 时无法购买车票，因此可以增加条件 $u\ge a_{i,j}$ 或 $u\ge b_{i,j}$。
这样优化后就可以愉快地 AC 这道题。
### std
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int c,n,m,k,a[46][46],b[46][46],ans[46][46],dp[2][46][46][46][91];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
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;
for(int i=1;i<=n;i++){
c^=1;
memset(dp[c^1],0,sizeof(dp[c^1]));
for(int j=1;j<=m;j++){
ans[i][j]=dp[c][j][0][0][0];
for(int u=k;u>=a[i][j];u--){
for(int x=0;x<=n-i;x++){
for(int y=0;y<=m-j;y++){
int *p=&dp[c][j][x+1][y][u-a[i][j]];
*p+=dp[c][j][x][y][u];
if(*p>mod)*p-=mod;
}
}
}for(int u=k;u>=b[i][j];u--){
for(int x=0;x<=n-i;x++){
for(int y=0;y<=m-j;y++){
int *p=&dp[c][j][x][y+1][u-b[i][j]];
*p+=dp[c][j][x][y][u];
if(*p>mod)*p-=mod;
}
}
}if(i<n)
for(int u=0;u<=k;u++){
for(int x=1;x<=n-i;x++){
for(int y=0;y<=m-j;y++){
int *p=&dp[(c^1)][j][x-1][y][u];
*p+=dp[c][j][x][y][u];
if(*p>mod)*p-=mod;
}
}
}
if(j<m)
for(int u=0;u<=k;u++){
for(int x=0;x<=n-i;x++){
for(int y=1;y<=m-j;y++){
int *p=&dp[c][j+1][x][y-1][u];
*p+=dp[c][j][x][y][u];
if(*p>mod)*p-=mod;
}
}
}
}
}for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<ans[i][j]<<" ";
}cout<<"\n";
}return 0;
}
```
**别忘了取模，注意 $u,x,y$ 枚举时的初始值是多少。**