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

前置

有一个整数

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

也可以）。

CPP

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;
}