【動態規劃完全背包卡常】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，就解決。

擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標及時的反饋拉伸區（難度合適）專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功成功+反思=成功