这题跟常规的数位DP有所不同,因为样历数很多,所以不能每次都完整的状态DP一边,先说一下状态dp[i][s]表示i位,lis状态为s的状态,根据这个状态去转移,为了不每次都清空一次,对于每种k,在开一维,然后dp数组的含义变成,i位数字,状态s,要求k的答案,那么记忆化搜的时候,遇到小于的情况,就可以直接记忆化搜索,这样等于只需要在完全等于原数的一条路径上进行搜索即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int t, k; ll l, r; int bit[25], bn; int bitcount(int x) { if (x == 0) return 0; return bitcount(x>>1) + (x&1); } void get(ll x) { bn = 0; if (!x) bit[bn++] = 0; while (x) { bit[bn++] = x % 10; x /= 10; } } ll dp[25][1025][11]; int getnext(int s, int x) { int flag = 1; if (x == 0 && s == 0) return 0; for (int i = 0; i < 10; i++) { if (s&(1<<i) && x <= i) { s ^= (1<<i); s ^= (1<<x); flag = 0; break; } } if (flag) s ^= (1<<x); return s; } int to[1025][10], bitc[1024]; ll dfs(int u, int s, int k, int flag) { if (u == -1) return bitc[s] == k; ll &ans = dp[u][s][k]; if (ans != -1 && flag) return ans; ll tmp = 0; int end = flag ? 9 : bit[u]; for (int i = 0; i <= end; i++) { if (i < bit[u]) tmp += dfs(u - 1, to[s][i], k, 1); else tmp += dfs(u - 1, to[s][i], k, flag); } if (flag) ans = tmp; return tmp; } ll solve(ll x) { get(x); return dfs(bn - 1, 0, k, 0); } int main() { int cas = 0; memset(dp, -1, sizeof(dp)); for (int i = 0; i < 1024; i++) { bitc[i] = bitcount(i); for (int x = 0; x < 10; x++) to[i][x] = getnext(i, x); } scanf("%d", &t); while (t--) { scanf("%I64d%I64d%d", &l, &r, &k); printf("Case #%d: %I64d\n", ++cas, solve(r) - solve(l - 1)); } return 0; }