AcWing 1533. 1 的个数
原题链接
中等
作者:
炽热的
,
2023-03-15 12:22:30
,
所有人可见
,
阅读 186
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int len;
int nums[N], f[N][N];
int dfs(int pos, int cnt, int limit) {
if (!pos) return cnt;
if (!limit && ~f[pos][cnt]) return f[pos][cnt];
int up = limit ? nums[pos] : 9, res = 0;
for (int i = 0; i <= up; i ++ )
res += dfs(pos - 1, cnt + (i == 1), limit && i == up);
return limit ? res : f[pos][cnt] = res;
}
int calc(int x) {
memset(f, -1, sizeof f);
while (x) nums[ ++ len] = x % 10, x /= 10;
return dfs(len, 0, 1);
}
int main() {
int n; cin >> n;
cout << calc(n);
return 0;
}