題意：

　　先定義一個數的power value，把這個數看成一個字符串，他的最長上升子序列的長度就是他的power value，求某個區間內power value等于k的數的個數。

解法：

　　很顯然要數位DP，先考慮LIS的nlogn解法，我們用dp[len]記錄LIS長度為len時的最后一個數的大小，然后不斷更新這些值，讓每一個值都盡可能小，比如我現在的LIS是1 2 4 6，這時候下一個數是3,那么我們就要更新成1 2 3 6,讓前面的數盡可能的小，這樣就是為了能讓后面的數有更多的機會被加入。

　　同理，因為數字只有10個，我們可以狀態壓縮，記錄每個數字是否出現在當前的LIS中，然后根據這個狀態，用前面的辦法轉移就行了。

　　

　　dp[len][number][mask]記錄第len位數字是number當前LIS的狀態是mask的答案。狀態轉移可以預處理出來

1 #include<cstdio> 2 #include<cstring> 3 #include<bitset> 4 #include<cstdlib> 5 #include<cmath> 6 #include<iostream> 7 #include<string> 8 #include<vector> 9 #include<queue> 10 #include<deque> 11 #include<set> 12 #include<map> 13 #include<algorithm> 14 using namespace std; 15 typedef long long ll; 16 const int N = 20; 17 ll dp[N][10][1<<10][11]; 18 int hash[1<<10]; 19 int next[1<<10][10]; 20 int bit[N],K; 21 int go(int mask,int number){ 22 int pos = -1; 23 for(int i = number;i <=9;i++) 24 if(mask & (1<<i)){ 25 pos = i; 26 break; 27 } 28 if(pos == -1)mask |= 1<<number; 29 else{ 30 mask ^= 1<<pos; 31 mask |= 1<<number; 32 } 33 return mask; 34 } 35 void init(){ 36 memset(dp,-1,sizeof(dp)); 37 for(int i=0;i<1<<10;i++){ 38 hash[i] = 0; 39 for(int j=0;j<10;j++) 40 if(i&(1<<j))hash[i]++; 41 } 42 for(int i = 0;i < 1<<10;i++) 43 for(int j = 0;j < 10;j++) 44 next[i][j] = go(i,j); 45 for(int i = 0;i < 15;i++){ 46 // cout<<"cur "; 47 // cout<<(bitset<10>)i<<endl; 48 for(int j=0;j<10;j++){ 49 // cout<<"j = "<<j<<" "<<(bitset<10>)next[i][j]<<endl; 50 } 51 } 52 } 53 ll dfs(int pos,int number,int mask,bool isZero,bool flag){ 54 if(pos == 0)return hash[mask] == K; 55 if(flag && ~dp[pos][number][mask][K])return dp[pos][number][mask][K]; 56 ll ans = 0; 57 int u = flag ? 9:bit[pos]; 58 for(int d = 0;d <= u;d++){ 59 if(isZero && d == 0)ans += dfs(pos-1,d,0,1,flag || d < u); 60 else{ 61 ans += dfs(pos-1,d,next[mask][d],0,flag || d < u); 62 } 63 } 64 if(flag)dp[pos][number][mask][K] = ans ; 65 return ans; 66 } 67 ll solve(ll n){ 68 int len = 0; 69 while(n){ 70 bit[++len] = n % 10; 71 n /= 10; 72 } 73 return dfs(len,0,0,1,0); 74 } 75 int main(){ 76 init(); 77 ll L,R; 78 int T;cin >> T; 79 for(int cas = 1;cas <= T;cas++){ 80 cin >> L >> R >> K; 81 cout<<"Case #"<<cas<<": "<<solve(R) - solve(L - 1)<<endl; 82 } 83 return 0; 84 }

?

?

轉載于:https://www.cnblogs.com/silver-bullet/p/3259205.html

總結

以上是生活随笔為你收集整理的hdu 4352 XHXJ's LIS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。