HDU 4352 XHXJ's LIS - 状压dp + LIS

传送门

题目大意：

题目分析：

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

struct ioSys{

    inline ll read(){

        ll i = 0, f = 1; char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar())

            i = (i << 3) + (i << 1) + (ch - '0');

        return i * f;

    }

    inline void wr(int x){

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

    inline void operator >> (ll &x){

        x = read();

    }

    inline void operator << (int x){

        wr(x);

    }

}IO;

ll T;

ll l, r, k, len;

typedef long long ll;

ll dp[25][1050][15], s[25], to[1050][15], oneNum[1050];

inline void convert(ll x){

    len = 0;

    memset(s, 0, sizeof s);

    while(x) s[++len] = x % 10, x /= 10;

}

inline ll count(ll x){

    int ret = 0;

    while(x) ret++, x = x & (x - 1);

    return ret;

}

inline void init(){

    memset(dp, -1, sizeof dp);

    for(int i = 0; i <= (1 << 10) - 1; i++){

        for(int j = 0; j <= 9; j++){

            int  tmp = 0, p;

            for(p = j; p < 10; p++)

                if(i & (1 << p)) break;

            if(p == 10) tmp = i | (1 << j);

            else tmp = i ^ (1 << p) | (1 << j);

            to[i][j] = tmp;

        }

    }

    for(int i = 0; i <= (1 << 10) - 1; i++)

        oneNum[i] = count(i);

}

inline ll DP(int pos, int sta, bool limit, bool lead, int K){

    if(!limit && !lead && dp[pos][sta][K] != -1) return dp[pos][sta][K];

    if(pos == 0) return oneNum[sta] == k || (lead && K == 1);

    int high = limit ? s[pos] : 9;

    ll ret = 0;

    for(int i = 0; i <= high; i++){

        if(i == 0 && lead) ret += DP(pos - 1, 0, limit && (i == high), true, K);

        else

            ret += DP(pos - 1, to[sta][i], limit && (i == high), false, K);

    }

    if(!limit && !lead) dp[pos][sta][K] = ret;

    return ret;

}

int main(){

   T = IO.read();

   init();

   for(int t = 1; t <= T; t++){

       IO >> l, IO >> r, IO >> k;

       convert(r);

       ll ret1 = DP(len, 0, 1, 1, k);

       convert(l - 1);

       ll ret2 = DP(len, 0, 1, 1, k);

       printf("Case #%d: %I64d\n", t, ret1 - ret2);

   }

   return 0;

}