【題解】Zerojudge c543 - 四、階梯數字(ladder) (APCS 加強題)

題目連結

題目大意

定義階梯數字為從高位數往低位數看過去，每一位數字只會相等或變大，例如 $123$、$336699$。給定 $n$，求 $1 \sim n$ 中階梯數字的數量。

• $1 \leq n \leq 10^{100000}$

題解

本題為 digit DP 的經典題。我們希望可以用最少的狀態數量來分類數字。我們把 $n$ 反過來做。定義 $dp[i][j][true/false]$ 為長度為 $i$，最高位為 $j$，且目前 $i$ 個數字比 $n$ 的前 $i$ 個數字大或小的數字數量。枚舉所有的狀態和新增加的數字即可。最後只要把合法的狀態加起來就是答案了。其他實作的細節請參考程式碼。

順帶一提，g352 和 g396 也都可以運用 digit dp 的技巧解出。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1E9 + 7;

const int N = 1E5 + 5;

int dp[N][10][2];

int solve(string s) {
	int n = s.size();
	reverse(s.begin(), s.end());
	s = " " + s;
	memset(dp, 0, sizeof(dp));
	dp[0][9][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(bool big : {false, true}) {
			for(int last = 0; last < 10; last++) {
				for(int add = 0; add <= last; add++) {
					bool new_big = (add > s[i] - '0') || (add == s[i] - '0' && big);
					dp[i][add][new_big] = (dp[i][add][new_big] + dp[i - 1][last][big]) % MOD;
				}
			}
		}
	}
	long long ans = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < 10; j++) {
			ans += dp[i][j][false] + dp[i][j][true];
		}
	}
	for(int i = 1; i < 10; i++) {
		ans += dp[n][i][false];
	}
	return ans % MOD;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	while(cin >> s) {
		cout << solve(s) << "\n";
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge c543 - 四、階梯數字(ladder) (APCS 加強題)