数位DP-白红宇

数位DP

阅读量：6984 次

发布时间：2019-06-27

本文共 8930 字，大约阅读时间需要 29 分钟。

数位DP

嗯，作为一类比较自成一派的DP还是要学一下。

其实不是很难，主要通过记忆化搜索实现。

用例题来讲解吧。

第一道数位DP/洛谷三萌成就达成！

洛谷P3413 萌数

大意:求[l, r]中存在长度至少为2的回文子串的数的个数，对1e9+7取模。

r <= 10^1000

首先可以发现，回文串长度为2或3即可。

然后我们就设计状态：f[k][last][ll][0/1][0/1]表示后k位中，第k + 1位是last，第k + 2位是ll，k位之前是否已出现回文串，k位之前是否出现过非0数(不是全是前导0)，满足条件的数的个数。

枚举k位放什么即可。顺便更新一波状态。

注意有limit的时候记忆化无用，要往后算。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 const int N = 1010, MO = 1000000007; 6  7 int f[N][11][11][2][3], num[N]; 8  9 int DFS(int k, int last, int ll, int sta, int first, bool limit) {10     if(k == 0) {11         return sta;12     }13     if(!limit && f[k][last][ll][sta][first] != -1) {14         return f[k][last][ll][sta][first];15     }16     int ans = 0;17     int large = limit ? num[k] : 9;18     for(int i = 0; i <= large; i++) {19         if(sta) {20             ans += DFS(k - 1, i, last, sta, first, limit && (i == num[k]));21             ans %= MO;22         }23         else {24             int temp = 0;25             if(first == 1) {26                 temp = (i == last);27             }28             else if(first == 2) {29                 temp = (i == last) || (i == ll);30             }31             int second = first;32             if(i || first) {33                 second = std::min(2, second + 1);34             }35             ans += DFS(k - 1, i, last, temp, second, limit && (i == num[k]));36             ans %= MO;37         }38     }39     if(!limit) {40         f[k][last][ll][sta][first] = ans;41     }42     //printf("%d %d %d %d %d %d = %d \n", k, last, ll, sta, first, limit, ans);43     return ans;44 }45 46 char str[N];47 48 int main() {49     memset(f, -1, sizeof(f));50 51     scanf("%s", str);52     int n = strlen(str);53     for(int i = n - 1; i >= 0; i--) {54         num[n - i] = str[i] - '0';55     }56     int temp = 0;57     if(n > 1 || num[1]) {58         num[1]--;59         int t = 1;60         while(num[t] < 0) {61             num[t] += 10;62             num[t + 1]--;63             t++;64         }65         if(!num[n]) {66             n--;67         }68         temp = DFS(n, 10, 10, 0, 0, 1);69     }70 71     scanf("%s", str);72     n = strlen(str);73     for(int i = n - 1; i >= 0; i--) {74         num[n - i] = str[i] - '0';75     }76    77     int ans = DFS(n, 10, 10, 0, 0, 1) - temp;78     ans = (ans % MO + MO) % MO;79     printf("%d", ans);80     return 0;81 }

AC代码

洛谷P2657 windy数

大意：求[l, r]之中每两个相邻数码之差大于1的数的个数。

这还比前一道题水一点......

f[k][last][0/1]表示后k位，第k + 1位是last，k位之前是否全是0的满足条件的数的个数。

然后就过了。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 const int N = 20; 6  7 int f[N][10][2], num[N]; 8  9 int DFS(int k, int last, int sta, bool limit) {10     if(k == 0) {11         return 1;12     }13     if(!limit && f[k][last][sta]) {14         return f[k][last][sta];15     }16 17     int ans = 0;18     int large = limit ? num[k] : 9;19     for(int i = 0; i <= large; i++) {20         if(sta) {21             if(i <= last + 1 && i >= last - 1) {22                 continue;23             }24             ans += DFS(k - 1, i, sta, limit && (i == num[k]));25         }26         else {27             ans += DFS(k - 1, i, i > 0, limit && (i == num[k]));28         }29     }30 31     if(!limit) {32         f[k][last][sta] = ans;33     }34     //printf("%d %d %d %d %d \n", k, last, sta, limit, ans);35     return ans;36 }37 38 inline int solve(int x) {39     if(!x) {40         return 1;41     }42     int n = 0;43     while(x) {44         num[++n] = x % 10;45         x /= 10;46     }47     return DFS(n, 0, 0, 1);48 }49 50 int main() {51 52     int a, b;53     scanf("%d%d", &a, &b);54     printf("%d", solve(b) - solve(a - 1));55 56     return 0;57 }

AC代码

注意有一个细节：这两题(大部分)中，sta状态(就是之前是否全是0)其实可以只在DFS函数中传，而不在f数组中多开一维。

原理我还没想清楚呢......闲的没事还是加上好了，避免出锅。

洛谷P2518 计数

比较特立独行的一道题.....

大意：给你若干个数码，总和<=50，让你求比给定的某一个全排列字典序小的全排列数。

保证答案在long long内。

就相当于给定每个数个数的数位DP。

先开个桶。可以发现，按照上面的套路的话，!limit的时候可以直接用公式。

然后就直接过了......我的map其实没啥用，就比暴力快了0.1ms........

至于统计过程中爆long long...大家各显神通吧。我是分解质因数。也可以拆成若干个组合数相乘，避免除法。

1 #include 
      
         2 #include 
         3 #include 
        
           4   5 typedef long long LL;  6 const int N = 60;  7   8 struct STA {  9     int a[11]; 10     inline bool operator <(const STA &w) const { 11         for(int i = 0; i <= 10; i++) { 12             if(a[i] != w.a[i]) { 13                 return a[i] < w.a[i]; 14             } 15         } 16         return 0; 17     } 18     inline bool operator ==(const STA &w) const { 19         for(int i = 0; i <= 10; i++) { 20             if(a[i] != w.a[i]) { 21                 return 0; 22             } 23         } 24         return 1; 25     } 26 }bin; 27  28 std::map
         
           mp; 29 int p[N], cnt[N], top, num[N]; 30 char str[N]; 31 bool vis[N]; 32 std::map
          
           ::iterator it; 33  34 inline LL qpow(LL a, LL b) { 35     LL ans = 1; 36     while(b) { 37         if(b & 1) { 38             ans *= a; 39         } 40         a *= a; 41         b = b >> 1; 42     } 43     return ans; 44 } 45  46 inline void getp(int b) { 47     for(int i = 2; i <= b; i++) { 48         if(!vis[i]) { 49             p[++top] = i; 50         } 51         for(int j = 1; j <= top && i * p[j] <= b; j++) { 52             vis[i * p[j]] = 1; 53             if(i % p[j] == 0) { 54                 break; 55             } 56         } 57     } 58     return; 59 } 60  61 inline void add(int x, int v) { 62     //printf("add : %d %d \n", x, v); 63     for(int i = 1; i <= top && x > 1; i++) { 64         while(x % p[i] == 0) { 65             cnt[i] += v; 66             x /= p[i]; 67         } 68     } 69     return; 70 } 71  72 inline LL cal(int k) { 73     memset(cnt, 0, sizeof(cnt)); 74     for(int i = 2; i <= k; i++) { 75         add(i, 1); 76     } 77     for(int i = 0; i <= 9; i++) { 78         for(int j = 2; j <= bin.a[i]; j++) { 79             add(j, -1); 80         } 81     } 82     LL ans = 1; 83     for(int i = 1; i <= top; i++) { 84         if(cnt[i]) { 85             ans *= qpow(p[i], cnt[i]); 86         } 87     } 88     return ans; 89 } 90  91 LL DFS(int k, bool limit) { 92     if(k == 0) { 93         return 1; 94     } 95     it = mp.find(bin); 96     if(!limit && it != mp.end()) { 97         return it->second; 98     } 99     if(!limit) {100         LL ans = cal(k);101         mp[bin] = ans;102         return ans;103     }104     int large = limit ? num[k] : 9;105     LL ans = 0;106     for(int i = 0; i <= large; i++) {107         if(!bin.a[i]) {108             continue;109         }110         bin.a[i]--;111         ans += DFS(k - 1, limit && (i == num[k]));112         bin.a[i]++;113     }114     /*printf("%d %d %lld \n", k, limit, ans);115     for(int i = 0; i <= 9; i++) {116         printf("%d ", bin.a[i]);117     }118     puts("");*/119     return ans;120 }121 122 int main() {123     getp(50);124     scanf("%s", str);125     int n = strlen(str);126     for(int i = n - 1; i >= 0; i--) {127         num[n - i] = str[i] - '0';128         bin.a[num[n - i]]++;129     }130 131     printf("%lld\n", DFS(n, 1) - 1);132     return 0;133 }

AC代码

洛谷P2602 数字计数

大意：求在[l, r]之中每个数码出现了几次。

首先简化它，对每个数码分别做。

这里的状态是f[k][0/1]表示在后k位是否中含有数码aim的个数。aim是枚举的。

然后我们发现，如果我们当前选的数码恰好是aim，那么额外加上后面的总个数就行了。

1 #include 
      
        2 #include 
       
         3  4 typedef long long LL; 5 const int N = 20; 6  7 LL f[N][2], pw[N], s; 8 int num[N], aim; 9 10 LL DFS(int k, int sta, bool limit) {11     if(k == 0) {12         return sta == 0 && aim == 0;13     }14     if(!limit && f[k][sta] != -1) {15         return f[k][sta];16     }17     LL ans = 0;18     int large = limit ? num[k] : 9;19     for(int i = 0; i <= large; i++) {20         if(sta) {21             ans += DFS(k - 1, sta, limit && (i == num[k]));22         }23         else {24             ans += DFS(k - 1, i > 0, limit && (i == num[k]));25         }26         if(i == aim && (sta || i)) {27             if(limit && i == num[k]) {28                 ans += s % pw[k - 1] + 1;29             }30             else {31                 ans += pw[k - 1];32             }33         }34     }35     if(!limit) {36         f[k][sta] = ans;37     }38     return ans;39 }40 41 inline LL solve(LL x) {42     if(!x) {43         return !aim;44     }45     int n = 0;46     s = x;47     while(x) {48         num[++n] = x % 10;49         x /= 10;50     }51     return DFS(n, 0, 1);52 }53 54 int main() {55     LL a, b;56     scanf("%lld%lld", &a, &b);57     pw[0] = 1;58     for(int i = 1; i <= 15; i++) {59         pw[i] = pw[i - 1] * 10;60     }61 62     for(int i = 0; i <= 9; i++) {63         aim = i;64         memset(f, -1, sizeof(f));65         printf("%lld ", solve(b) - solve(a - 1));66     }67     return 0;68 }

AC代码

参考资料：红太阳的博客。

总结一下：基本都是套路......做的都是板题.......

哇！他们考的都好难啊.....要命哇...

：一个比较独特的数位DP。

转载于:https://www.cnblogs.com/huyufeifei/p/10009452.html

你可能感兴趣的文章