1049 Counting Ones (30分)

这题就是一道数位dp的一道题，直接用数学做就行了，分别统计个位、十位、百位上1的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e6+10;

int main() {
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt","r",stdin);
#endif

    long long N;
    cin>>N;
    long long cnt=0;
    cnt+=N/10;
    if (N%10) cnt++;
    long long base=100;
    while (base/10<=N) {
        long long t=N/base;
        long long tmp=base/10;
        long long k=N/tmp%10;
        if (k>1) t++;
        else if (k==1) cnt+=(N%tmp)+1ll;
        cnt+=t*tmp;
        base*=10;
    }
    cout<<cnt<<endl;
    return 0;
}