DDOSvoid's Blog

hdu 4352 XHXJ's LIS

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=4352

dp套dp入门题

Solution

我们考虑求LIS的方法，由于在本题中LIS的每位数字都是已知且长度小于等于十，所以我们可以直接状压来记录求LIS的d数组

由于多组数据，为了避免每次初始化，可以把询问中的长度也记录下来

时间复杂度为 $O(len^4 2^{10})$

可以提前预处理状态转移，做到 $O(len^3 2^{10})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 20
#define maxm 11
#define ll long long
using namespace std;

int n; ll a, b; 

int L[1 << maxm];
void init() {
    int M = (1 << maxm) - 1, m = 10; 
    for (int S = 1; S <= M; ++S) 
        for (int i = 1; i <= m; ++i) L[S] += S >> i - 1 & 1;
}
 
int calc(int S, int k) {
    for (int i = k; i < 10; ++i) 
        if (S >> i & 1) { S ^= 1 << i; break; } 
    S |= 1 << k; return S; 
} 
    

ll f[maxn][1 << maxm][maxm]; int K, d[maxn], len; 
ll dfs(int pos, int lead, int limit, int S, int k) {
    if (!pos) return L[S] == k; 
    if (!lead && !limit && ~f[pos][S][k]) return f[pos][S][k];
    int up = limit ? d[pos] : 9; ll ans = 0;
    for (int i = 0; i <= up; ++i) {
        if (lead && !i) { ans += dfs(pos - 1, 1, 0, 0, k); continue; }
        ans += dfs(pos - 1, 0, limit && i == d[pos], calc(S, i), k);
    }
    if (!lead && !limit) f[pos][S][k] = ans;
    return ans;
}

ll solve(ll x) { len = 0;
    while (x) { 
        d[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, 1, 1, 0, n);
}

int icase; 
void work() { 
    cin >> a >> b >> n;
    printf("Case #%d: %lld\n", ++icase, solve(b) - solve(a - 1)); 
}

int main() {
    int T; cin >> T; init(); memset(f, -1, sizeof f); 
    while (T--) work(); 
    return 0;
}