T12 XHXJ's LIS (HDU4352)

苹果蓝17 · 2020-05-04 22:21:49 · 个人记录

T12 XHXJ's LIS (HDU4352)

~~经过前面几题，想必大家对状压很熟悉了~~

HDU传送门

题意简述

求区间 [L,R] 中，各位数字组成的序列的 LIS （最长上升子序列）恰好为 k 的数字个数。

延伸：在区间 [L,R] 中任意选出一个数，求各位数字组成的序列的 LIS （最长上升子序列）的期望值。

数据范围

1 \leq T \leq 10^4

0 < L \leq R <2^{63}-1$ , $1 \leq k \leq 10

题解

思路

和前面几题类似，还是考虑对于单个数如何求各位数组成的 LIS

但是这里不能用那个 O(n^2) 的算法（用 f[i] 表示前 i 个的 LIS ），不但时间不优，而且空间不够

有一种 O(nlogn) 的算法。不记录前 i 个的 LIS ，而是考虑用 f[i] 记录 LIS 为 i 时最后一个数的最小值（只是为了方便理解，实际上无需记录）

一个一个地加入，用 ans 表示目前的 LIS

如果加入的这个数是最大的，那么 ans++ ，f[ans]=a[i]

否则，在前面的 a[j](j<i) 中找到最小的，大于等于这个数的，把所有这样的替换成 a[i] ，再更新一次 f

为什么呢？

对于 i 前面的，既然 a[j] 已经是大于等于 a[i] 中最小的了，它变成 a[i] 不会改变大小关系，也不会影响答案。
对于 i 后面的，（如果不换）选用 a[i] 显然比选用 a[j] 更优，替换掉相当于等效

举个栗子，25413

加入2, 5，f[1]=2，f[2]=5
加入4，4之前最小的 \geq4 的是5，因此把5换成4，24413，f[2]=4
加入1，1之前最小的 \geq1 的是2，因此把2换成1,14413
加入3，3之前最小的 \geq3 的是4，因此把4都换成3，13313，f[2]=3
所以 LCS=2

当然光是这样空间是 10^{10} ，想都不用想

其实这种dp有个特性，它只关心每个数有没有出现过，却不关心具体的位置与个数

于是我们可以直接记录每个数是否出现过，空间只有 2^{10}=1024

最后的 LIS 即是出现的数的总个数了

这是状压部分，当然既然要求 [L,R] 的，还得套个数位dp

发现状压和数位的加入顺序都是从高位到低位，直接dp就好了

做法

设 f[i][mac] 为枚举到第i位，状压为mac时的方案数

不过询问数有 10^4 ，每次清零太慢了

不如再加一维 k 表示 LIS 为 k ，直接记录不清零

数位dp我想不用再细说了吧

注意事项

这里前导0是有影响的，注意判断
状态更新时注意如果原来是0，加入0是无需更新的（要特判）

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll t,l,r,k;
ll a[22],f[22][1100][11];
ll dp(ll pos,ll mac,bool lead,bool eq){//数位dp模板 
    if(pos==0){//如果枚举完了 
        ll tot=0;
        for(ll i=0;i<=9;i++) if((mac>>i)&1) tot++;
        if(tot==k) return 1;//如果LIS为k 
        else return 0;
    }
    if(!eq && !lead && f[pos][mac][k]!=-1) return f[pos][mac][k];
    ll ed=eq?a[pos]:9,ret=0;//模板 
    for(ll i=0;i<=ed;i++){
        ll new_mac=mac;
        if(!lead || i){//注意不为0或加上的数不为0才需要转移 
            for(ll j=i;j<=9;j++)
                if((mac>>j)&1){
                    new_mac^=(1<<j);
                    break;
                }
            new_mac|=(1<<i);
        }
        ret+=dp(pos-1,new_mac,lead && !i,eq && i==a[pos]);
    }
    if(!eq && !lead) f[pos][mac][k]=ret;
    return ret;
}
ll solve(ll x){//数位dp模板 
    memset(a,0,sizeof(a));
    while(x){
        a[++a[0]]=x%10;
        x/=10;
    }
    return dp(a[0],0,1,1);
}
int main(){
    memset(f,-1,sizeof(f));//注意初始化 
    scanf("%lld",&t);
    for(ll i=1;i<=t;i++){
        scanf("%lld%lld%lld",&l,&r,&k);
        printf("Case #%lld: %lld\n",i,solve(r)-solve(l-1));
    }
}