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

题意：

求有多少个数，进行若干次变换后，能变为

n

。
规则：每次加上这个数的数位和。

思路：

由于规律促使小的数变大，永远不会变小，不难发现计算顺序是从小到大的递推。这是动态规划的板子题。
我们可以直接从

f[i]

推到

f[i+calc(i)]

，其中 calc(i) 表示

i

的数位和。
需要注意的是

f[i]

初始值为

1

，因为

i

可以自己转移到

i

。

代码：

CPP

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

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

文章操作

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

题意：

思路：

代码：

相关推荐

评论

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