HDU-4352 XHXJ's LIS(数位dp+状压)

B - XHXJ's LIS

  HDU - 4352 

题意：给定一个区间[l,r]，问区间内有多少个数满足：它的每一位上的数字所组成的序列的最长上升子序列的长度恰好是k
题解：数位dp,考虑到最长上升子序列的O(nlogn)的解法，因为只有0~9共10种数字，可以用状态压缩：二进制下S的第i位如果是1，则表示i已经在子序列里面，如果S中有k个1那么就满足要求。每次更新S时，找到子序列中第一个不小于i的数，把这个数删去再把i放入子序列中。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[25][1<<11][11];
int k,a[25];
int getNum(int S){   //得到最长上升自序列的长度
    int ret=0;
    while(S) {
        if(S&1) ret++;
        S>>=1;
    }
    return ret;
}
int upSta(int S,int j){   //更新状态
    for(int i=j;i<=9;i++)
        if(S&(1<<i)) return (S^(1<<i))|(1<<j);
    return S|(1<<j);
}
LL dfs(int i,int S,int mark){
    if(i==0) return getNum(S)==k;
    if(mark==0&&dp[i][S][k]>=0) return dp[i][S][k];
    int mx=mark?a[i]:9;
    LL ret=0;
    for(int j=0;j<=mx;j++)ret+=dfs(i-1,S==0&&j==0?0:upSta(S,j),mark&&j==mx);
    if(mark==0) dp[i][S][k]=ret;
    return ret;
}
LL solve(LL x){
    int len=0;
    while(x) {a[++len]=x%10;x/=10;}
    return dfs(len,0,1);
}
int main(){
    int T;
    LL l,r;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    for(int cas=1;cas<=T;cas++){
        scanf("%I64d%I64d%d",&l,&r,&k);
        printf("Case #%d: %I64d\n",cas,solve(r)-solve(l-1));
    }
    return 0;
}