HDU 4352

tiberius 2019-08-31 原文

题意略。

思路：

这一发A得实在是难能可贵。因此我要记录一下。

首先这个题很明显是个数位dp，其难点在于如何知道填到当前这一位时，我的最长上升子序列是多长。

如果是一个简单的求最长上升子序列的题，我们一般会在一个数组中使用二分法，每次查找新来的这个数字在这个数组中应该排什么位置。

但是我们记录状态不可能还带着一个数组。回过头来仔细研究一下这种数组的性质，你会发现它数组内的元素一定是从前到后严格递增的。

那其实我们可以只记录在当前状态时，这个数组中都有哪些元素就可以了，因为反正是两两不同且严格递增的。

又考虑到这个数组中只可能存在0~9这10个数，因此我们可以状态压缩一下。

从这个角度来说，本题同时考察了状压dp和数位dp。

1.要设置前导0，在无前导0的情况下，0可以计入状态集合；在有前导0的情况下，0不可以计入。因为09这种上升序列不合题意。

2.dp[pos][state][k] 表示考虑到pos位，排序数组中的状况是state，最长上升子序列长度为k。

代码附上：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn0 = 20;
 5 const int maxn1 = (1<<10) + 5;
 6 const int maxn2 = 15;
 7 
 8 LL dp[maxn0][maxn1][maxn2],l,r;
 9 int a[maxn0],store[maxn0],k,t,tail,T;
10 
11 int cnt1(int x){
12     int ret = 0;
13     while(x){
14         x = x & (x - 1);
15         ret += 1;
16     }
17     return ret;
18 }
19 void process(LL x){
20     tail = 0;
21     while(x){
22         a[tail++] = int(x % 10);
23         x /= 10;
24     }
25 }
26 inline void decode(int x){
27     t = 0;
28     for(int i = 0;(x>>i) > 0;++i){
29         int temp = (x>>i);
30         if(temp & 1) store[t++] = i;
31     }
32     store[t] = maxn0;
33 }
34 inline int encode(){
35     int ret = 0;
36     for(int i = 0;i < t;++i) ret += (1<<store[i]);
37     return ret;
38 }
39 LL dfs(int pos,int state,bool limit,bool lead,int kk){
40     
41     if(pos == -1) return cnt1(state) == k ? 1 : 0;
42     if(!limit && !lead && dp[pos][state][kk] != -1) return dp[pos][state][kk];
43     
44     int up = limit ? a[pos] : 9;
45     LL ret = 0;
46     for(int i = 0;i <= up;++i){
47         decode(state);
48         int idx = lower_bound(store,store + t,i) - store;
49         if(idx + 1 > k) break;
50         
51         store[idx] = i;
52         t = max(idx + 1,t);
53         
54         int nstate = (i == 0 && lead) ? state : encode();
55         ret += dfs(pos - 1,nstate,limit && i == up,lead && i == 0,kk);
56     }
57     if(!limit && !lead) dp[pos][state][kk] = ret;
58     return ret;
59 }
60 
61 int main(){
62     
63     scanf("%d",&T);
64     memset(dp,-1,sizeof(dp));
65     int cas = 1;
66     while(T--){
67         scanf("%lld%lld%d",&l,&r,&k);
68         
69         process(l - 1);
70         LL ans0 = dfs(tail - 1,0,true,true,k);
71         
72         process(r);
73         LL ans1 = dfs(tail - 1,0,true,true,k);
74         
75         printf("Case #%d: %lld\n",cas++,ans1 - ans0);
76     }
77     return 0;
78 }