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

· · 题解

前置

传送门

AC记录

题意

有一个整数 N(1\le N\le10^6)，求有多少个大于 1、小于 N 的数经过多次操作后变为 N。

操作为：将当前所持整数用十进制表示，将其各位数字之和加到该整数上。

思路

这是一道很好的动态规划题。

我们定义 f_i 记为当前有 f_i 个大于 1、小于 i 的数经过多次操作后变为 i。

然后就是状态转移。

假设这个这个数的个位数字之和记为 g(x)，那么更新过后的数字就会变为 x+g(x)。

那么我们可以基本定下来：

f_{x+g(x)}\rightarrow f_{x+g(x)}+f_x+1

可能就有人问：“为什么要加一”？

答：因为本身（就是原数字）也可以。

答案最后别忘了加一（因为自身 N 也可以）。

Code

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int t=i,sum=i;
        while(t) sum+=t%10,t/=10;
        f[sum]+=f[i]+1;
    }
    cout<<f[n]+1;
    return;
}