第一道数位dp
之前看了讲解视频,然后知道了数位dp的基本代码结构
主要是求一个dp推导,然后再特判最终情况。
这里的dp推导,不是直接循环将dp推导出来
(我看的视频里是用循环推导的dp)
这里面用循环的话,编码难度会很高
因此这里选择的是dfs记忆化递归!
然后,在特判最终情形就好了。
数为dp最为困难的就是dp的推导!!!
#include<cstring> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int max_n = 120; const int N = 14; typedef long long ll; ll f[N][max_n][max_n][max_n]; ll dfs(int pos, int tar, int red, int mod) { if (f[pos][tar][red][mod] != -1)return f[pos][tar][red][mod]; if (pos == 1)return f[pos][tar][red][mod] = !(red | mod); f[pos][tar][red][mod] = 0; ll cur = 1; for (int i = 1;i < pos - 1;++i)cur *= 10; for (int i = 0;i <= red && i <= 9;++i) { f[pos][tar][red][mod] += dfs(pos - 1, tar, red - i, (mod + cur * i % tar) % tar); }return f[pos][tar][red][mod]; } ll dp(ll n) { if (!n)return 0; vector<int> nums; while (n) { nums.push_back(n % 10); n /= 10; } ll res = 0; ll last = 0; int sum = 0; ll cur = 1; for (int i = 1;i <= nums.size();++i)cur *= 10; for (int i = nums.size() - 1;i >= 0;--i) { cur /= 10; int x = nums[i]; if (x) { for (int y = 0;y < x;++y) { for (int tar = max(1,sum + y);tar <= 108;++tar) { res += dfs(i + 1, tar, tar - y - sum, (y * cur + last) % tar); } } } last += x * cur; sum += x; if (i == 0) { res += (last % sum == 0); } } return res; } int main() { ios::sync_with_stdio(0); for (int i = 0;i < N;++i)for (int j = 0;j < max_n;++j)for (int k = 0;k < max_n;++k)for (int o = 0;o < max_n;++o)f[i][j][k][o] = -1; int t;cin >> t; for (int i = 1;i <= t;++i) { ll n;cin >> n; cout << "Case " << i << ": " << dp(n) << endl; } }