[HDOJ5787]K-wolf Number（数位DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5787

题意：求[L,R]区间内的数字，使得所有长度为k的子数列内所有数位都不同。

K<=5的所以可以直接记录到前k个数字的值是多少。dp(l,p1,p2,p3,p4)分别记录就可以了。

弱智了WA了好几发，因为k每次取值是不一样的，所以dp数组还是应当放在while里清空。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 22;
 6 int k;
 7 int digit[maxn];
 8 LL dp[maxn][12][12][12][12];
 9 LL l, r;
10 
11 bool ok(int a, int b, int c, int d, int e) {
12     if(k == 2) return e != d;
13     if(k == 3) return e != d && e != c;
14     if(k == 4) return e != d && e != c && e != b;
15     if(k == 5) return e != d && e != c && e != b && e != a;
16 }
17 
18 LL dfs(int l, int p1, int p2, int p3, int p4, bool flag) {
19     if(l == 0) return p4 != 10;
20     if(!flag && ~dp[l][p1][p2][p3][p4]) return dp[l][p1][p2][p3][p4];
21     LL ret = 0;
22     int pos = flag ? digit[l] : 9;
23     for(int i = 0; i <= pos; i++) {
24         if(i == 0 && p4 == 10) ret += dfs(l-1,10,10,10,10,flag&&(i==pos));
25         else if(ok(p1,p2,p3,p4,i)) ret += dfs(l-1,p2,p3,p4,i,flag&&(i==pos));
26     }
27     if(!flag) dp[l][p1][p2][p3][p4] = ret;
28     return ret;
29 }
30 
31 LL f(LL x) {
32     if(l <= 0) return 0;
33     int pos = 0;
34     while(x) {
35         digit[++pos] = x % 10;
36         x /= 10;
37     }
38     return dfs(pos,10,10,10,10,true);
39 }
40 
41 int main() {
42     // freopen("in", "r", stdin);
43     while(~scanf("%I64d%I64d%d",&l,&r,&k)) {
44         memset(dp, -1, sizeof(dp));
45         printf("%I64d
", f(r)-f(l-1));
46     }
47     return 0;
48 }