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

定义

f_x

为有多少个数经过若干次操作可以变成

x

，而我们的

f_x

没有算上

x

本身（不进行操作的情况），因此最终答案为

f_x + 1

。
设一个数

a

经过操作后可以得到数

b

，得到转移方程：

f_b = f_b + f_a + 1

。对于每个

b

，若其大于

n

，那么统计它也没有意义，可以加特判跳过。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e6 + 10;
int n;
int f[N];
inline int add(int k){
	int cnt = 0;
	while(k){
		cnt += k % 10;
		k /= 10;
	}
	return cnt;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++){
		if(i + add(i) > n)continue;
		f[i + add(i)] += f[i] + 1;
	}
	cout << f[n] + 1;
	return 0; 
}

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

文章操作

代码：

相关推荐

评论

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