比赛 新年快乐 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 倒计时 最终得分 100
用户昵称 xuyuqing 运行时间 0.059 s
代码语言 C++ 内存使用 3.75 MiB
提交时间 2026-02-13 10:11:40
显示代码纯文本

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

constexpr int N = 20;

long long n;
long long nums[N];
long long cc;
long long pw10[N];
long long dp[N][N][N];
long long magic[N][N][N];

void dfs (long long maxn, long long len, long long u, long long now) {
	if (dp[maxn][len][u] || magic[maxn][len][u]) {
		return;
	}

	if (len == 1) {
		if (now == 0 || maxn > now) {
			dp[maxn][len][u] = 0;
			magic[maxn][len][u] = now;
		}
		else {
			dp[maxn][len][u] = 1;
			magic[maxn][len][u] = 0;
		}
		return;
	}

	long long newMaxn = maxn;
	long long newLen = len - 1;
	long long newU = u;
	long long newNow = now % pw10[newLen];
	long long num = (u == 10) ? nums[len] : 9;

	for (long long i = num; i >= 0; i--) {
		newMaxn = max (maxn, i);
		dfs (newMaxn, newLen, newU, newNow);

		dp[maxn][len][u] += dp[newMaxn][newLen][newU];
		newNow = i * pw10[newLen] + magic[newMaxn][newLen][newU];
		
		if (i != 0) {
			newU = 10 + magic[newMaxn][newLen][newU] - newMaxn;
			newNow -= newMaxn;
			newNow %= pw10[newLen];
			dp[maxn][len][u]++;
		}
		else {
			magic[maxn][len][u] = magic[newMaxn][newLen][newU];
		}
	}
}

int main () {

	freopen ("countdown.in", "r", stdin);
	freopen ("countdown.out", "w", stdout);

	cin >> n;
	
	if (n == 0) {
		cout << 0 << endl;
		return 0;
	}

	long long t = n;
	while (t) {
		cc++;
		nums[cc] = t % 10;
		t /= 10;
	}

	pw10[0] = 1;
	for (int i = 1; i <= cc; i++) {
		pw10[i] = pw10[i - 1] * 10;
	}

	dfs (0, cc, 10, n);
	
	cout << dp[0][cc][10] << endl;

	return 0;
}