[数据结构与算法]算法竞赛进阶指南- 月之谜

迭代版本，根据原书的题解编写。

int func(int R)
{
	int res = 0;
	vector<int> arr;
	int r = R;
	int N = 0;//确定R有N位
	while (r){
		N ++ ;
		int mod = r % 10;
		arr.push_back(mod);
		r /= 10;
	}

	vector<vector<vector<vector<int>>>> dp(6,
		vector<vector<vector<int>>>(50,
		vector<vector<int>>(50, vector<int>(50, 0))));

	//边界
	for (int p = 0; p <= 9; p++)
	{
		for (int k = 1; k <= 45; k++)
		{
			int l = p%k;
			dp[1][p][k][l] = 1;
			dp[0][0][k][0] = 1;
		}
	}


	for (int i = 2; i <= N; i++){
		for (int j = 1; j <= 9 * i; j++){
			for (int k = 1; k <= j; k++){
				for (int l = 0; l < k; l++){
					for (int p = 0; p <= 9; p++){
						int mod = (int)(l - p*pow(10, i - 1)) % k;
						while (mod < 0)mod += k;
						if (j >= p)
							dp[i][j][k][l] += dp[i - 1][j - p][k][mod];
						else{
							break;
						}				
					}
				}
			}
		}
	}

	//cout << dp[2][8][8][0];
	//cout << endl;
	
	for (int sum = 1; sum <= 9*N; sum++){
		int t = 0;
		int q = 0;
		for (int i = N; i; i--){
			bool flag = false;
			for (int p = 0; p <= 9; p++){
				if (t+p <= sum){
					if (p < arr[i - 1]){
						int mod = (int)(sum - q - p*pow(10, i - 1)) % sum;
						while (mod < 0)mod += sum;
						res += dp[i-1][sum - t - p][sum][mod];
					}else{
						if (i == 1){
							int mod = (int)(sum - q - p*pow(10, i - 1)) % sum;
							while (mod < 0)mod += sum;
							res += dp[i - 1][sum - t - p][sum][mod];
						}
						t += p;
						q = (int)(q + p*pow(10, i - 1)) % sum;
						break;
					}
				}
				else{
					flag = true;break;
				}}
			if (flag)break;
		}}
	return res;
}

网上也有大神通过记忆化搜索求解。这里提供copy来的代码，shame on me.

long long f[20][170][170];
int a[20];

long long dfs(int pos, int sum, int val, int mod, int lim)
{
	long long ans = 0;
	if (pos == -1) return sum == 0 && val == 0;
	if ((pos + 1) * 9<sum) return 0; // 剪枝而已无须在意
	if (!lim && f[pos][sum][val] != -1) return f[pos][sum][val];
	int up = lim ? a[pos] : 9;
	for (int i = 0; i <= up; i++)
	{
		if (sum<i) break;
		ans += dfs(pos - 1, sum - i, (val * 10 + i) % mod, mod, lim && i == up);
	}
	if (!lim) f[pos][sum][val] = ans;
	return ans;
}

long long solve(long long n)
{
	int cnt = 0;
	long long ans = 0;
	memset(a, 0, sizeof(a));
	while (n)
	{
		a[cnt++] = n % 10;
		n /= 10;
	}
	for (int i = 1; i <= 9 * cnt; i++)
	{
		memset(f, -1, sizeof(f));
		ans += dfs(cnt - 1, i, 0, i, 1);
	}
	return ans;
}

大家可以对比看一下这两种方法的结果。

int main() 
{
	int n = 100;
	int res1 = func(n);
	cout << res1 << endl;

	long long res2 = solve(n);
	cout << res2 << endl;

	system("pause");
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖