【动态规划完全背包卡常】P9743 「KDOI-06-J」旅行|普及+

本文涉及知识点

C++动态规划完全背包
C++记忆化搜索

「KDOI-06-J」旅行

题目描述

小 C 在 C 国旅行。

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

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

对于所有 $1≤i<n,1≤j≤m1\leq i<n,1\leq j\leq m$ ， $(i, j)$ 到 $(i + 1, j)$ 有一段由 L 公司修的单向铁路；
对于所有 $1≤i≤n,1≤j<m1\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≤x≤n,1≤y≤m1\leq x\leq n,1\leq y\leq m$ ，求他花 $k$ 元钱并在城市 $(x, y)$ 结束旅行的方案数，对 $998244353998\ 244\ 353$ 取模。

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

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

样例 #1

样例输入 #1

样例输出 #1

0 0 0
0 1 5
1 3 5

提示

【样例解释 #1】

到 $(3, 1)$ 的方案有：

在 $(1, 1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2, 1)$ ；在 $(2, 1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3, 1)$ 。

到 $(2, 2)$ 的方案有：

在 $(1, 1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2, 1)$ ；在 $(2, 1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(2, 2)$ 。

到 $(3, 2)$ 的方案有：

在 $(1, 1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1, 2)$ ；在 $(1, 2)$ 购买 $2$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2, 2)$ ；乘坐 L 公司的铁路到 $(3, 2)$ 。
在 $(1, 1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1, 2)$ ；乘坐 L 公司的铁路到 $(2, 2)$ ；在 $(2, 2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3, 2)$ 。
在 $(1, 1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 L 公司的铁路到 $(2, 1)$ ；乘坐 Z 公司的铁路到 $(2, 2)$ ；在 $(2, 2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3, 2)$ 。

到 $(2, 3)$ 的方案有：

在 $(1, 1)$ 购买 $1$ 张 L 公司的铁路票和 $2$ 张 Z 公司的铁路票。在此之后，有 $3$ 种方案可以从 $(1, 1)$ 乘坐两公司的铁路到 $(2, 3)$ 。
在 $(1, 1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1, 2)$ ；在 $(1, 2)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票。在此之后，有 $2$ 种方案可以从 $(1, 2)$ 乘坐两公司的铁路到 $(2, 3)$ 。

【样例 #2】

见选手目录下的 travel/travel2.in 与 travel/travel2.ans。这个样例满足测试点 $7∼87\sim 8$ 的条件限制。

【样例 #3】

见选手目录下的 travel/travel3.in 与 travel/travel3.ans。这个样例满足测试点 $11$ 的条件限制。

【数据范围】

对于所有数据保证： $1≤n,m≤451\leq n,m\leq45$ ， $1≤k,ai,j,bi,j≤901\leq k,a_{i,j},b_{i,j}\leq90$ 。

测试点编号	$n, m$	$k$	$a_{i,j}$	$b_{i,j}$
$1∼31\sim3$	$≤3\leq3$	$≤5\leq5$	$= 1$	$= 1$
$4∼64\sim6$	$≤10\leq10$	$≤10\leq10$	$= 1$	$= 40$
$7∼87\sim8$	$≤40\leq40$	$≤30\leq30$	$= 1$	$= 45$
$9∼109\sim10$	$≤15\leq15$	$≤15\leq15$	$≤15\leq15$	$≤15\leq15$
$11$	$≤15\leq15$	$≤30\leq30$	$≤30\leq30$	$≤30\leq30$
$12$	$≤20\leq20$	$≤40\leq40$	$≤40\leq40$	$≤40\leq40$
$13∼1513\sim15$	$≤25\leq25$	$≤50\leq50$	$≤50\leq50$	$≤50\leq50$
$16$	$≤30\leq30$	$≤60\leq60$	$≤60\leq60$	$≤60\leq60$
$17$	$≤35\leq35$	$≤70\leq70$	$≤70\leq70$	$≤70\leq70$
$18∼1918\sim19$	$≤40\leq40$	$≤80\leq80$	$≤80\leq80$	$≤80\leq80$
$20$	$≤45\leq45$	$≤90\leq90$	$≤90\leq90$	$≤90\leq90$

动态规划+完全背包

动态规划的状态表示

dp[r][c][rr][d][m] 表示到达(r,c)，向右移动的票剩余rr张，向下移动的票剩余d张，钱剩余m的方案数。
空间复杂度：O(n⁵)，由于只能右下，不能左上，故不会有环。
r,c都改成从0开始。第i个城市 c = i -r，故可省略c。空间复杂度：O(n⁴)。利用滚动空间降低空间复杂度，状态数没变。

动态规划的填表顺序

for i = 1 to (R+C-2) for(r = 0 to R-1 ) for(d =0 to K) for(rr =0 to K) for( m = k to 0)

动态规划的状态转移

为了避免买票顺序不同的造成的重复，我们先买向下的票，再买向右的票。
对于每种状态dp[r][d][rr][k]，可以分三种子状态：
一，(r,i-r)所在城市没有买票。二，买了向下的票，没有买向右的票。三，买了向右的票，可能买了向下的票，也可能没有买向下的票。
前两种子状态有4种操作：右移下移买向右的票买向下的票。
第三种子状态有三种操作：右移下移买向右的票

pre[i-1]个城市，cur表示第i个城市

cur[r][rr][d][m] = pre[r-1][rr][d+1][m]+pre[r][rr+1][d][m] 当前城市没买票。
如果rr > 0，m+1张相右的车票<=k
cur[r][rr][d][m] += cur[r][rr-1][d][m+1张相右的车票] 操作一
d > 0,m+1张相向下的车票<=k
cur[r][rr][d][m] += cur[r][rr][d-1][m+1张相下的车票] 操作二

单个状态时间复杂度：O(1)

动态规划的初始状态

pre全部为0，pre[0][0] 如果钱和票数，能够一致则为1。否则为0。

动态规划的返回值

dp[x][y][0][0][0]
注意：本题3秒，O(4545454590) 约等于3.7e8，需要注意细节。

代码

核心代码

最后一个样例超时

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for(int i=0;i < n ;i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}C1097Int  operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();return *this;}bool operator==(const C1097Int& o)const{return m_iData == o.m_iData;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return (m_iData + MOD) % MOD;}
private:int m_iData = 0;;
};class Solution {public:typedef  C1097Int<998244353> BI;vector<vector<int>> Ans(const int K, vector<vector<int>>& a, vector<vector<int>>& b) {const int R = a.size(), C = a[0].size();const int S1 = (K+1);const int S2 = S1*(K + 1);const int S3 = S2 * (K + 1);const int S4 = S3*R;const int SizeBtye = sizeof(BI) * S4;auto pre = new BI[S4];memset(pre, 0, SizeBtye);for (int i = 0; i * a[0][0] <= K; i++) {int tmp = 0;for (int j = 0; (tmp=j * b[0][0] + i * a[0][0]) <= K; j++) {pre[S2*i+S1*j + K-tmp] = 1;}}auto cur = new BI[S4];auto cu2 = new BI[S4];vector<vector<int>> ans(R,vector<int>(C));for (int i = 1; i <= min(R + C - 2,K); i++) {memset(cur, 0, SizeBtye);memset(cu2, 0, SizeBtye);for (int r = max(0, i - (C - 1)); r <= min(i, R - 1); r++) {const int c = i - r;auto pr = cur + S3 * r;for (int d = 0; i+d <= K; d++){const auto pd = pr + S2 * d;for (int rr = 0; (i+rr+d) <= K; rr++) {const auto prr = pd + S1 * rr;const auto pre1 = S3 * r + S2 * d + S1 * (rr + 1);const auto pre2 = S3 * (r - 1) + S2 * (d + 1) + S1 * rr;const auto cur1 = S3 * r + S2 * (d - 1) + S1 * rr;const auto cur2 = S3 * r + S2 * d + (rr - 1) * S1;const auto cu21 = r * S3 + S2 * d + S1 * rr;for (int k = 0; (i+rr+d+k) <= K; k++) {if (rr + 1 <= K) {//本站没有买票,上一站是左边prr[k] += pre[pre1 +k];}if ((r>0)&&(d + 1 <= K)) {//本站没有买票，上一站是上边prr[k] += pre[pre2+k];}if ((d > 0) && (k + a[r][c] <= K)) {//本站至少买了一张向下的票prr[k] += cur[cur1 + k + a[r][c]];prr[k] -= cu2[cur1 + k + a[r][c]];}if ((rr > 0) && (k + b[r][c] <= K)) {//本站至少买了一张向右的票prr[k] += cur[cur2 + k + b[r][c]];cu2[cu21+k] += cur[cur2 +k + b[r][c]];}}}}ans[r][c] = pr[0].ToInt();}swap(pre, cur);}		return ans;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	int n, m, K;cin >> n >> m >> K;vector<vector<int>> a(n, vector<int>(m)), b(n, vector<int>(m));for (int r = 0; r < n; r++){for (int c = 0; c <m ; c++) {cin >> a[r][c];}}for (int r = 0; r < n; r++){for (int c = 0; c < m; c++) {cin >>b[r][c];}}auto res = Solution().Ans(K, a, b);
#ifdef _DEBUG/*printf("K=%d", K);Out(a, ",a=");Out(b, ",b=");*/
#endif // DEBUG	for (auto& v : res) {for (auto& i : v) {printf("%d ", i);}printf("\r\n");}return 0;
}

单元测试

	int K;vector<vector<int>> a, b;TEST_METHOD(TestMethod11){K = 5, a = { {3,2,1},{2,1,3},{1,3,2} }, b = { {1,2,3},{2,3,1},{3,1,2} };auto res = Solution().Ans(K,a,b);AssertV({ {0,0,0},{0,1,5},{1,3,5} }, res);}TEST_METHOD(TestMethod12){K = 3, a = { {1,1,1},{1,1,1},{1,1,1} }, b = { {1,1,1},{1,1,1},{1,1,1} };auto res = Solution().Ans(K, a, b);AssertV({ {0,0,0},{0,0,17},{0,17,0} }, res);}TEST_METHOD(TestMethod13){K = 28, a.assign(38,vector<int>(40,1)), b.assign(38, vector<int>(40, 45));auto res = Solution().Ans(K, a, b);AssertEx(0, res[28][12]);}TEST_METHOD(TestMethod4){K = 2, a.assign(1, vector<int>(4, 1)), b.assign(1, vector<int>(4, 45));auto res = Solution().Ans(K, a, b);AssertV({ {0,0,0,0} }, res);}TEST_METHOD(TestMethod5){K = 2, a.assign(4, vector<int>(1, 1)), b.assign(4, vector<int>(1, 45));auto res = Solution().Ans(K, a, b);AssertV({ {0},{0},{2},{0}}, res);}

卡常

反复尝试了多次，瓶颈在memset，直接将一个memset改成将修改的值清0，就解决。

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功