题解：P14337 [JOI2020 预选赛 R2] 求和 / Digit Sum

· · 题解

题解：P14337 [JOI2020 预选赛 R2] 求和 / Digit Sum

题意：

求有多少个数，进行若干次变换后，能变为 n 。
规则：每次加上这个数的数位和。

思路：

由于规律促使小的数变大，永远不会变小，不难发现计算顺序是从小到大的递推。这是动态规划的板子题。
我们可以直接从 f[i] 推到 f[i+calc(i)] ，其中 calc(i) 表示 i 的数位和。
需要注意的是 f[i] 初始值为 1 ，因为 i 可以自己转移到 i 。

代码：

#include<bits/stdc++.h>

using namespace std;

int n,f[1000050];
inline int calc(int x){ //计算数位和 
    int res = 0;
    while(x){
        res+=(x%10);
        x/=10;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i = 1;i <= n;++i){
        f[i]++; //注意自己也可以转移到自己 
        f[i+calc(i)]+=f[i];
    }
    cout<<f[n];
    return 0;
}