HDU 4352 XHXJ's LIS，hduxhxj
XHXJ's LIS
題意:求出給定區間[L,R] (0<L<=R<263-1 and 1<=K<=10) 中數滿足LIS(非連續嚴格遞增子序列)為K的個數？
如區間[123,321]中的124的LIS為3；
<1> 總結數位DP的優化方式:
例: 1.在codeforces 的beautiful number 中，要求滿足能被自己的每一個非零數字整除的數的個數。這時構造出lcm，當高位mod(所有元素的lcm直接優化到2520)後將會出現很多重疊的子問題，這就是狀態的轉移；當然裡面各種的lcm只需存儲即可；
2.本題:首先要知道給定一個序列，知道怎麼求解LIS，如 1 2 4 6 ，當加入3時，這時長度為3的LIS的最小值為3，而不是4.(使用數組存儲的是[長度] = minval),但是本題並不是這樣的LIS，這需要模糊看待才能將不一樣的高位看成是相同的，才能有重疊的子結構.
在dfs開始時，state為0，這時如果前面加入的是98之後加入1，那麼按照原始的LIS長度是為1的，但是這裡長度看成3，為什麼?因為這裡state存儲的只是狀態，就是說dfs到pos-1位時，只知道前面有哪些值，並不需要知道加入的前後順序~~那這就將排序問題簡化為了組合問題，這才是優化的本質。這也是為什麼說state中的1個數就是LIS的值；(故意按照遞增排列的)
但是還有問題:
- 能不能直接加入一個數，而不將前面的狀態刪減？不能，因為當你只是添加該位置的數時，就會發現在最後判斷是否state的1的個數為k時，只能是出現數字為k的值。如在樣例中你只能是 221,133,144這樣的值，而198這樣的值不行。所以必須要刪減。
- 刪減的個數？題解中是只刪一個，如果要將當前插入的值放到最後，是需要將將後面更大的值全部刪掉的，但是這是一個組合問題，只需要優化該數所在的數值即可。即如果前面的數為1 2 4 5 現在插入的是3,3是LIS長度為3的點，之前該點的值是4，就把4改成3.開始我想的是把最大值刪去，在把當前的值插入是不是這樣的優化更好呢?但是發現裡面少了很多值.(你改後把樣例輸入發現結果為125,少計算了如191，190，291,290,292這些數)；
- 是否能前置0?1.當state還是0時，是不能將0加入狀態，但是當state中已經加入的元素，就可以；對情況1，這時就是數值的前置0，加了會和後面同值的數重復，對於情況2,這時看做為前面LIS的優化相同長度的值，可以。
到此，就可以確定dfs的參數為4個pos,state,edge(原來就有)，還要考慮一個是否有前置0的zero參數。
(使用的是內置函數__builtin_popcount()來計算數位1的個數)
![]()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)= 0;i < (n);i++)
#define MS1(a) memset(a,-1,sizeof(a))
typedef long long ll;
ll dp[20][1<<10][11];
int bit[20],K;
int newstate(int state,int v)
{
for(int i = v;i < 10;i++)
if(state &(1 << i)) return (state ^ (1 << i))|(1<<v);
return state|(1<<v);
}
ll dfs(int pos,int state,bool edge,bool zero)
{
if(pos == -1) return __builtin_popcount(state) == K;
if(!edge && dp[pos][state][K] != -1) return dp[pos][state][K];
int end = edge ? bit[pos]:9;
ll ans = 0;
for(int i = 0;i <= end;i++){
ans += dfs(pos - 1,(zero && i == 0)?0:newstate(state,i),edge && i == end,zero && i == 0);
}
if(!edge) dp[pos][state][K] = ans;
return ans;
}
ll calc(ll x)
{
int tot = 0;
while(x){
bit[tot++] = x%10;
x /= 10;
}
return dfs(tot - 1,0,1,1);
}
int main()
{
int T,kase = 1;
MS1(dp);
cin>>T;
while(T--){
ll L,R;
scanf("%I64d%I64d%d",&L,&R,&K);
printf("Case #%d: %I64d\n",kase++,calc(R) - calc(L-1));
}
}
View Code
