把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

HDU4352 XHXJ’s LIS
题目大意：给两个数l，r（范围为1<<64），和k（范围为10），求范围内有多少个数位上lis长度为k的数。

解：

看见l和r就知道是数位dp，不过转移方程推起来很困难，原因在于lis的转移是需要知道前面整个数列的，这样就失去了后效性，但是由于lis长度最大只为10，所以我们可以直接状压作为状态，这样就可以转移了。
最后再次吹一波雨巨的数位dp记忆化dfs板子，让原来很难搞的对数字求值变得简单无脑了……
Dp[i][j][k]表示当数位为i并且lis状态为j，lis长度为k时的数字数量（k这一维可以省，但没必要，没去省是自以为能省下10倍的时间复杂度，后来发现并不行，见下文）。注意首0是不算做数字的，所以k等于要求值时还要检查一下j是否等于0。转移的过程和lis相同，由于只有10位所以也不需要二分了。
值得一提的是dp的值如果只设置i，j两维的话，对于不同的k会传出不同的k值，所以实际上还不如不省来得方便，题目卡了32MB的空间，10的地方不能开15只能开11，满满的恶意。
也算是长见识了，把三个完全不在同一个世界的dp联系到一起了。

一开始没想到状压，想传数组的方法，但传数组就没法记忆化了……实际上，看见本题较小的参数（64,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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;using namespace std;
ll k;
ll dp[25][1025][11][11], digits[25];
string getbin(int n) {
    if (n == 0)return "0";
    string res = "";
    int b = 1;
    while (b <= n) {
        b <<= 1;
    }
    b >>= 1;
    int tmp = n;
    while (b) {
        if (tmp >= b) {
            res += "1";
            tmp -= b;
        }
        else res += "0";
        b >>= 1;
    }
    return res;
}
ll dfs(int pos, int flag, int state, int kk) {
    if (pos == -1) {
        if (kk == k && state != 0) {
            return 1;
        }
        else return 0;
    }
    if (!flag && dp[pos][state][kk][k] != -1) {
        return dp[pos][state][kk][k];
    }
    int fmax;
    if (flag == 0)fmax = 9;
    else fmax = digits[pos];
    ll res = 0;
    int ct = 9;
    while (ct >= 0 && ((1 << ct) & state) == 0)ct--;
    for (int i = 0; i <= fmax; i++) {
        if (state == 0) {
            if (i != 0)
                res += dfs(pos - 1, flag == 1 && i == fmax, state + (1 << i), 1);
            else
                res += dfs(pos - 1, flag == 1 && i == fmax, 0, 0);
            continue;
        }
        int st = state;
        if (i > ct)res += dfs(pos - 1, flag == 1 && i == fmax, st + (1 << i), kk + 1);
        else {
            int act = 9;
            int minu = -1;
            while (act >= i) {
                if (((1 << act) & st) != 0) {
                    minu = act;
                }
                act--;
            }
            if (i == act)
                res += dfs(pos - 1, flag == 1 && i == fmax, st, kk);
            else
                res += dfs(pos - 1, flag == 1 && i == fmax, st + (1 << i) - (1 << minu), kk);

        }
    }
    if (flag == 0)dp[pos][state][kk][k] = res;
    return res;
}
ll cnt(ll a) {

    ll tmp = a;
    int xb = 0;
    while (tmp) {
        digits[xb++] = tmp % 10;
        tmp /= 10;
    }
    return dfs(xb - 1, 1, 0, 0);
}
int main() {
    cfast;
    int t;
    cin >> t;
    int ct = 0;
    inc(i, 0, 25) {
        inc(j, 0, 1025) {
            inc(k, 0, 11) {
                inc(m, 0, 11)
                    dp[i][j][k][m] = -1;
            }
        }
    }
    while (t--) {
        ct++;
        ll a, b;
        cin >> a >> b >> k;
        cout << "Case #" << ct << ": " << cnt(b) - cnt(a - 1) << endl;
    }
}//((()