HDU 4352（LIS+数位dp）

数位dp基础题。
思路来自kuangbin。
代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int maxn = 2e5 + 10;
const int maxm = 1e4 + 10;
const ll mod = 998244353;

ll l, r, k, a[20], f[20][1025][11];

int get_num(ll x) {
    int t = 0;
    while (x) {
        if (x & 1)++t;
        x >>= 1;
    }
    return t;
}

int get_pos(int pos, int x) {
    for (int i = x; i <= 9; ++i) {
        if (pos & (1 << i)) {
            return ((pos ^ (1 << i)) | (1 << x));
        }
    }
    return (pos | (1 << x));
}

ll dp(int p, int pos, bool e, bool z) {
    if (p == 0)return get_num(pos) == k;
    if (!e && f[p][pos][k] != -1)return f[p][pos][k];
    ll ans = 0;
    for (int i = 0; i <= (e ? a[p] : 9); ++i) {
        ans += dp(p - 1, (z && i == 0) ? 0 : get_pos(pos, i), e && (i == a[p]), z && (i == 0));
    }
    if (!e)f[p][pos][k] = ans;
    return ans;
}

ll solve(ll x) {
    memset(a, 0, sizeof a);
    int len = 0;
    while (x) {
        a[++len] = x % 10;
        x /= 10;
    }
    return dp(len, 0, 1, 1);
}

int main() {
    __;
    memset(f, -1, sizeof f);
    int _;
    cin >> _;
    for (int sce = 1; sce <= _; ++sce) {
        cin >> l >> r >> k;
        cout << "Case #" << sce << ": " << solve(r) - solve(l - 1) << endl;
    }
    return 0;
}