AtCoder Beginner Contest 029 D - 1

問題リンク
atcoder.jp

考えたこと
1以上N以下の自然数に含まれる1の数を数え上げればよいためこれは桁dpで解くことができる.

状態の持ち方としては,
dp[i][j][k] := i番目までを見た時, （jはtightかどうか）1をk個もつような数字の個数

とする. なお, 桁数はせいぜい9なので, ある数字がもつ1の数も9が最大.

#include <bits/stdc++.h>

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);
    
    string s; cin >> s;
    ll dp[15][2][10]={0};

    dp[0][0][0]=1;
    for(int i=0; i<s.size(); i++){

        int num = s[i] - '0';

        for(int j=0; j<2; j++){
            int ma = 10;

            if(j == 0){
                ma = num + 1;
            }

            for(int d=0; d<ma; d++){

                for(int k=0; k<10; k++){

                    dp[i+1][j | (d != num)][k + (d == 1)] += dp[i][j][k];
                }
            }
        }
    }
    
    int ans = 0;
    for(int i=0; i<10; i++){
        ans += (dp[s.size()][0][i]+dp[s.size()][1][i])*i;
        
    }
    cout << ans << endl;
    return 0;
}