数位DP

CF204A

题目链接
https://codeforces.com/problemset/problem/204/A
题目大意

模板讲解

数位DP模板

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, t;
ll l,r;
string s;
ll memo[20][10][10];
ll dfs(int i, int first,int last,bool is_limit, bool is_num)
{
    if(i == m)
    {
        if(is_num && first == last) return 1;
        else                        return 0;
    }
    if(!is_limit && is_num && memo[i][first][last] != -1) return memo[i][first][last];
    ll res = 0;
    int up = is_limit ? s[i] - '0' : 9;
    if(!is_num) {
        res = dfs(i + 1,0,0,false,false);
        for(int d = 1;d <= up;++d){
            res += dfs(i + 1,d,d,is_limit && d == up,true);
        }
    }else{
        for (int d = 0; d <= up; ++d)
            res += dfs(i + 1,first, d,is_limit && d == up, true);
    }
    if (!is_limit && is_num)
        memo[i][first][last] = res;
    return res;
}
void solve() {
    cin >> l >> r;

    memset(memo,-1,sizeof(memo));
    s = to_string(l - 1);
    m = s.size();
    ll ans1 = dfs(0,0,0,true,false);

    memset(memo,-1,sizeof(memo));
    s = to_string(r);
    m = s.size();
    ll ans2 = dfs(0,0,0,true,false);
    cout << ans2 - ans1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    t = 1;
    for (int _ = 0; _ < t; _++)
        solve();
    return 0;
}