hdu4352---XHXJ's LIS(상태 압축 디지털 dp)

/************************************************************************* > File Name: hdu4352.cpp > Author: ALex > Mail: [email protected] > Created Time: 2015 02 24      10 55 05  ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

LL dp[40][15][(1 << 10) + 10];
int bit[40];
int k;

int get_one (int sta)
{
    int cnt = 0;
    while (sta)
    {
        cnt += (sta & 1);
        sta >>= 1;
    }
    return cnt;
}

int get_sta (int sta, int d)
{
    for (int i = d; i <= 9; ++i)
    {
        if (sta & (1 << i))
        {
            sta &= ~(1 << i);
            break;
        }
    }
    sta |= (1 << d);
    return sta;
}

LL dfs (int cur, int sta, bool flag, bool zero)
{
    if (cur == -1)
    {
        if (zero)
        {
            return 0;
        }
        return get_one (sta) == k;
    }
    if (!flag && ~dp[cur][k][sta])
    {
        return dp[cur][k][sta];
    }
    int end = flag ? bit[cur] : 9;
    LL ans = 0;
    for (int i = 0; i <= end; ++i)
    {
        if (zero && !i)
        {
            ans += dfs (cur - 1, 0, flag && (i == end), 1);
        }
        else if (zero && i)
        {
            ans += dfs (cur - 1, (1 << i), flag && (i == end), 0);
        }
        else
        {
            int newsta = get_sta(sta, i);
            ans += dfs (cur - 1, newsta, flag && (i == end), 0);
        }
    }
    if (!flag)
    {
        dp[cur][k][sta] = ans;
    }
    return ans;
}

LL calc (LL n)
{
    int ret = 0;
    memset (bit, 0, sizeof(bit));
    while (n)
    {
        bit[ret++] = n % 10;
        n /= 10;
    }
    return dfs (ret - 1, 0, 1, 1);
}

int main ()
{
    int t;
    int icase = 1;
    scanf("%d", &t);
    memset (dp, -1, sizeof(dp));
    while (t--)
    {
        LL l, r;
        scanf("%lld%lld%d", &l, &r, &k);
        printf("Case #%d: ", icase++);
        printf("%lld
", calc (r) - calc (l - 1));
    }
    return 0;
}