hdu4352 XHXJ's LIS

题目描述

把$[L,R]$内每个数字看成字符串,求满足最长上升子序列长度为$K$的串个数。

输入格式

First a integer T(T<=10000),then T lines follow, every line has three positive integer L,R,K.(0<L<=R<263-1 and 1<=K<=10).

输出格式

For each query, print "Case #t: ans" in a line, in which t is the number of the test case starting from 1 and ans is the answer.

样例输入

1
123 321 2

样例输出

Case #1: 139 

分析

要记录当前最长上升子序列的状态,我们可以使用$O(n\log n)$求LIS的方法,记录每个长度的结尾数字最小值,这些值组成一个上升序列。当加入数字$x$时,就把$\ge x$的最小数改为$x$。

因为只有$10$个数字,可以使用一个$10$位二进制数描述LIS的状态。然后就可以数位dp了。

不过,因为此题多组数据,对每组数据重新数位dp会超时。我们可以用记忆化的思想,有些求过的信息就不必再求。比如,当前状态没顶到边界时,相当于边界对答案没有影响,每次访问到当前状态时答案都是一样的,就可以把答案记录下来。

顺便提一下,数位dp用记忆化搜索的写法其实是逆推(从低位到高位),不过写法是顺着写的。

复杂度$O(明显能过)$。

代码

#include <bits/stdc++.h>
typedef long long ll;

int bin[11];
ll f[25][1024][11];
int m;
int a[25], len;

int getLen(int s) {
    int rtn = 0;
    for (int i = 0; i < 10; i++)
        if (s & bin[i]) rtn++;
    return rtn;
}

int trans(int s, int x) {
    for (int i = x; i <= 9; i++) {
        if (s & bin[i]) {
            s ^= bin[i];
            break;
        }
    }
    return s |= bin[x];
}

ll dfs(int i, int s, bool p) {
    if (i == 0) return getLen(s) == m;
    if (!p && f[i][s][m] != -1) return f[i][s][m];
    ll ans = 0;
    for (int j = 0, lim = (p ? a[i] : 9); j <= lim; j++)
        ans += dfs(i-1, !s && !j ? 0 : trans(s, j), p&&j==lim);
    if (!p) f[i][s][m] = ans;
    return ans;
}

ll calc(ll n) {
    ll t = n;
    for (len = 0; t; t /= 10)
        a[++len] = t % 10;
    return dfs(len, 0, true);
}

ll work() {
    ll l, r;
    scanf("%lld%lld%d", &l, &r, &m);
    return calc(r) - calc(l-1);
}

int main() {
    bin[0] = 1;
    for (int i = 1; i <= 10; i++)
        bin[i] = bin[i-1] << 1;
    memset(f, -1, sizeof f);

    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++)
        printf("Case #%d: %lld\n", cas, work());
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论