# 12678 - Count 1s
>author: Utin
###### tags: `dynamic program`
---

## Brief
建表

## Solution 0

#include <stdio.h>

int dp[1000005];

int main() {
    int N, tail = 1;
    scanf("%d", &N);
    while (N--) {
        int a, b;
        scanf("%d %d", &a, &b);
        for (int i = tail; i <= b; i++) {
            int tmp = i, amount = 0;
            while (tmp > 0) {
                if (tmp % 10 == 1) amount++;
                tmp /= 10;
            }
            dp[i] = dp[i-1] + amount;
        }
        if (tail < b + 1) tail = b + 1;
        printf("%d\n", dp[b] - dp[a-1]);
    }
}

// Utin

## Reference