ABC 29 D - 1 ( 桁DP )

D: 1 - AtCoder Beginner Contest 029 | AtCoder
桁DP は応用が利くなぁー（満足）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e9 + 9;
const int MAXP = 10;
typedef unsigned long long ull;
#define rep( i, a ) for(int i = 0; i < (int)( a ); ++i)

string s;

ull dp[ MAXP ][ 2 ][ 10 ];

void solve(){
    memset( dp, 0, sizeof(dp) );
    dp[ 0 ][ 0 ][ 0 ] = 1;
    rep( i, s.size() ) rep( j, 2 ) rep( k, 10 ){
        int lim = j ? 9 : s[ i ] - '0';
        rep( d, lim + 1 )
            dp[ i + 1 ][ j || d < lim ][ k + ( d == 1 ) ]
            += dp[ i ][ j ][ k ];
    }
    ull ans = 0;
    rep( j, 2 ) rep( k, 10 )
        ans += dp[ s.size() ][ j ][ k ] * k;
    cout << ans << endl;
}

int main(){
    cin >> s;
    solve();
    return 0;
}