HDU 4352

水深无声 2023-08-17 16:37 97阅读 0赞

题意略。

思路：

这一发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 }

转载于:https://www.cnblogs.com/tiberius/p/11439548.html