題意：
一個數自身的最長子序列=每一位都是一個數字然後求的LIS
問區間內有多少個數 自身的最長子序列==k
思路：
因為自身的最長子序列至多=10，且由0~9組成，所以狀壓10個二進制表示0~9中哪些數字已經用過
dp[i][j] 表示長度為i的數字，最長子序列中出現的數字狀態j的方法數。由於詢問數=K，也存下來避免重復計算。
#include#include #include #include using namespace std; typedef long long ll; const int N = 66; int siz[1 << 10], nex[1 << 10][10]; // nex[i][j]表示已經用了i狀態的序列，再加入數字j且使得序列狀態不變會變成的狀態 int bit[20], K; //因為K只有10，所以構成這個序列的最長也就是0~9,所以用一個二進制表示0~9中哪些已經用過了 ll dp[N][1<<10][11];//dp[len][high][state][lis];長度為len，最高位為high，已使用過的有效子序列的狀態為state,最長上升子序列為lis ll dfs(int len, int state, bool zero, bool flag){ if (len == 0)return siz[state] == K; if (!flag && dp[len][state][K] != -1)return dp[len][state][K]; ll ans = 0; int end = flag ? bit[len] : 9; for (int i = 0; i <= end; i++) ans += dfs(len - 1, (zero&&i == 0) ? 0 : nex[state][i], zero&&i == 0, flag&&i == end); if (!flag)dp[len][state][K] = ans; return ans; } ll solve(ll x){ int len = 0; for (ll tmp = x; tmp; tmp /= 10)bit[++len] = tmp % 10; return dfs(len, 0, 1, 1); } int find_nex(int status, int num){ for (int i = num; i < 10; i++) if (status&(1 << i))return(status ^ (1 << i)) | (1 << num); return status | (1 << num); } int main() { memset(dp, -1, sizeof dp); for (int i = 0; i < 1 << 10; i++){ siz[i] = 0; for (int j = 0; j < 10; j++) { if (i&(1 << j))siz[i]++; nex[i][j] = find_nex(i, j); } } int T, Cas = 1; scanf(%d, &T); while (T-- > 0){ ll l, r; cin >> l >> r >> K; printf(Case #%d: %I64d , Cas++, solve(r) - solve(l - 1)); } return 0; }
