XHXJ's LIS HDU - 4352 | 数位dp

时隔两个月重新看这道状压dp，还是比较容易理解的。状压dp大同小异，记忆化搜索、limit记录、状态压缩。。

题意：
这题意思就是给你一个LL范围内的区间，问你在这个区间内最长递增子序列长度恰为K的数有多少个？
分析：
1、结合nlogn求LIS进行状态压缩。
eg: ( 0 1 2 3 4 5 6 7 8 9)
0 1 1 0 1 0 0 0 0 0 (state)
以上state表示长度为1的上升序列末尾最小为1， 长度为2的...为2， 长度为3的....为4，也即用1的个数表示上升序列的长度，用位数表示末尾最大数。如果下一个数为3， 则新的状态为01110..
2、dp[i][j][k]表示对第i位，前几位的状态为j， LIS = k而且当前的limit为0的时候，接下来几位随意取数一共有多少个数满足。
3、注意已经处理过的位如果都是0的情况，也即前导零的处理。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(a) cout << "debug :" << a << endl
#define fi first
#define se second
const int maxn = 1e6;
const int inf = 0x3f3f3f3f;
ll l, r, k;
ll dp[20][5000][20];
int v[100];

int getnum(ll state)
{
    int num = 0;
    while(state) num += (state & 1), state >>= 1;
    return num;
}

int newstate(ll state, int v)
{
    for(int i = v; i < 10; i++) if(state & (1 << i)) return state ^ (1 << i) | (1 << v) ;
    return state | (1 << v);
}

ll dfs(int pos, ll state, bool valid, bool limit)
{
    if(!pos) return getnum(state) == k;
    if(!limit && ~dp[pos][state][k]) return dp[pos][state][k];
    int up = limit ? v[pos] : 9;
    ll res = 0;
    for(int i = 0; i <= up; i++)
    {
        bool isvalid = valid | i;
        res += dfs(pos - 1, isvalid ? newstate(state, i) : false, isvalid, limit && i == up);
    }
    if(!limit) dp[pos][state][k] = res;
    return res;
}

ll work(ll x)
{
    int pos = 0;
    while(x)
    {
        v[++pos] = x % 10;
        x /= 10;
    }
    return dfs(pos, 0, 0, 1);
}


int main()
{
    int t; cin >> t;
    int cases = 0;
    mem(dp, -1);
    while(t--)
    {
        scanf("%lld%lld%lld", &l, &r, &k);
        printf("Case #%d: %lld\n", ++cases, work(r) - work(l - 1));
    }
}