自动搬运

查看原文

来自洛谷，原作者为

	Eddie08012025 减训减训

搬运于2025-08-24 22:51:23，当前版本为作者最后更新于2025-01-26 15:35:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

基本思路

首先，看到此题数据范围 $n,m\le 45,k\le 90$ 很小，可以想到做一个高复杂度的 dp。

$dp_{i,j,x,y,u}$ 表示到达格子 $(i,j)$，还有 $x$ 张 L 公司的车票与 $y$ 张 Z 公司的车票，此时剩余 $u$ 元钱的方案数。

考虑如何转移，转移方程大概可以分成两个部分：

1. 在格子 $(i,j)$ 购买车票，购买一张 L 公司的铁路票花费 $a_{i,j}$ 元，购买一张 Z 公司的铁路票花费 $b_{i,j}$ 元。得：

2. 在格子 $(i,j)$ 花费一张车票乘坐铁路，乘坐 L 公司的铁路会从 $(i,j)$ 到达 $(i+1,j)$ 并花费一张 Z 公司的铁路票，乘坐 Z 公司的铁路会从 $(i,j)$ 到达 $(i,j+1)$ 并花费一张 Z 公司的铁路票。得：

如果你不加任何优化直接 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

#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$ 枚举时的初始值是多少。