题目大意：让你求l到r 之间数位的最长上升子序列的个数为k 的数的数量。
思路：用状态压缩模拟求最长上升子序列的过程，因为最多不超过10个所以可以压缩， 用dp[ i ][ j ][ k ]表示数位为i，最长上升子序列的状态为j，
最后最长上升序列为k的方案数。
#include<bits/stdc++.h> #define ll long long using namespace std; ll f[20][1<<11][11]; ll dig[20],tot,k; ll cal(ll s,ll u,ll &len) { ll i; for(i=u;i<10;i++) if(s&(1<<i)) break; if(i<10) { s^=(1<<i); s^=(1<<u); } else s^=(1<<u),len++; return s; } ll dp(ll pos,ll s,ll len,bool limit,bool lead) { if(pos==-1) return len==k; if(!limit && f[pos][s][k]!=-1) return f[pos][s][k]; ll up=limit? dig[pos]:9; ll ans=0; for(ll i=0;i<=up;i++) { ll nx_s,nx_len=len; if(lead && i==0) nx_s=0; else nx_s=cal(s,i,nx_len); ans+=dp(pos-1,nx_s,nx_len,limit && i==up,lead && i==0); } if(!limit) f[pos][s][k]=ans; return ans; } ll solve(ll x) { tot=0; while(x) { dig[tot++]=x%10; x/=10; } return dp(tot-1,0,0,true,1); } int main() { memset(f,-1,sizeof(f)); ll T; scanf("%I64d",&T); for(ll cas=1;cas<=T;cas++) { ll l,r; scanf("%I64d%I64d%I64d",&l,&r,&k); ll ans1=solve(r); ll ans2=solve(l-1); printf("Case #%I64d: %I64d ",cas,ans1-ans2); } return 0; }