首页 > 代码库 > 数位DP入门
数位DP入门
HDU 2089 不要62
DESC: 问l, r范围内的没有4和相邻62的数有多少个。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 int dp[10][5]; 8 9 /* 10 3种状态： 11 0：前i位不含有不吉利数字 的数 的个数 12 1：前i位不含有不吉利数字且第i+1位数字是6 的数 的个数 13 2：前i位含有不吉利数字 的数 的个数 14 */ 15 16 //int dfs(int i, int s, bool e) { 17 // if (i==-1) return s==target_s; 18 // if (!e && ~dp[i][s]) return dp[i][s]; 19 // int res = 0; 20 // int u = e?num[i]:9; 21 // for (int d = first?1:0; d <= u; ++d) 22 // res += dfs(i-1, new_s(s, d), e&&d==u); 23 // return e?res:f[i][s]=res; 24 //} 25 26 int num[10]; 27 int len; 28 29 int dfs(int pos, int s, bool e) { 30 if (pos == 0) return s != 2; //遍历完之后 判断当前数字是否是不吉利数 31 if (!e && dp[pos][s]) return dp[pos][s]; 32 int sum = 0; 33 int maxm = e?num[pos]:9; 34 35 for (int d = 0; d <= maxm; ++d) { 36 if (s == 0) { 37 if (d == 4) sum += dfs(pos-1, 2, e&&(maxm == d)); 38 else if (d == 6) sum += dfs(pos-1, 1, e&&(maxm == d)); 39 else sum += dfs(pos-1, 0, e&&(maxm == d)); 40 } 41 else if (s == 1) { 42 if (d == 4 || d == 2) sum += dfs(pos-1, 2, e&&(maxm == d)); 43 else if (d == 6) sum += dfs(pos-1, 1, e&&(maxm == d)); 44 else sum += dfs(pos-1, 0, e&&(maxm == d)); 45 } 46 else if (s == 2) sum += dfs(pos-1, 2, e&&(maxm == d)); 47 } 48 return e?sum:dp[pos][s]=sum; 49 } 50 51 int solve(int x) { 52 len = 1; 53 while(x) { 54 num[len++] = x%10; 55 x /= 10; 56 } 57 len -= 1; 58 return dfs(len, 0, 1); 59 } 60 61 int main() { 62 int n, m; 63 // cout << solve(100) << endl; 64 memset(dp, 0, sizeof(dp)); 65 while(~scanf("%d%d", &n, &m)) { 66 if (n == 0 && m == 0) break; 67 int l = solve(n-1); 68 int r = solve(m); 69 int ans = r - l; 70 printf("%d\n", ans); 71 } 72 return 0; 73 }
CF 55D Beautiful numbers 数位DP+离散化
DESC：如果一个数能整除它每一位上的数字，那么这个数叫做美丽数。问 l, r范围内的美丽数有多少个。
状态：dp[20][2600][55]; // dp[i][j][k] = x表示前i位mod2520的值为j 且最小公倍数是lcms[k] 的美丽数有多少个。
lcms[]是1~9的所有可能产生的最小公倍数的映射数组。
因为1~9能产生的最大公倍数是2520，又x%y==0 等价于x%y%z == 0在z是y的因子时成立。所以我们只需要维护前i个数mod2520的值，就可以知道前i个数mod1~9的值。
即第二维压缩到2520。
判断当前数字是否是beautiful number等价于判断当前数是否mod (前i位的最小公倍数==0)。
所以我们需要维护前i位的最小公倍数。
而1~9能产生的最小公倍数位最大值位2520，小于55个。所以可以离散化，即第三维压缩到55。
开始设计的状态是：dp[20][2]表示前i位是或不是beautiful number。中间用一个num数组标记当前值mod(1~9)的值，最后判断是否是beautiful number。
但是这样前i位的值就受后面的值的影响，不能记忆化了。遂超时。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #define LL long long 6 using namespace std; 7 8 const int maxn = 2520; 9 10 LL dp[20][2600][55]; // dp[i][j][k] = x表示前i位mod2520的值为j 且最小公倍数是lcms[k] 的美丽数有多少个。 11 int num[20]; 12 int lcms[2600]; 13 14 int gcd(int a, int b) { 15 return (b>0?gcd(b, a%b):a); 16 } 17 18 int ggcd(int a, int b) { 19 if (a == 0) return b; 20 else if (b == 0) return a; 21 return (a*b)/gcd(a, b); 22 } 23 24 void getLcms() { //初始化lcms[] 25 memset(lcms, -1, sizeof(lcms)); 26 int num = 1; 27 for (int i=1; i*i<=maxn; ++i) { 28 if (maxn%i==0 && lcms[i] == -1) { //能整除i 29 lcms[i] = num++; 30 int temp = maxn / i; 31 if (lcms[temp] == -1) 32 lcms[temp] = num++; 33 } 34 } 35 } 36 37 LL dfs(int pos, int pre, int lcm, bool lim) { // 当前位 前面i位mod2520的值 前面i-1位的lcm 当前位是否到最后一个数 38 if (pos == -1) return (pre%lcm==0); // 搜索到最后一位 39 if (!lim && dp[pos][pre][lcms[lcm]] != -1) return dp[pos][pre][lcms[lcm]]; // 记忆化搜索 40 int mnum = (lim==0?9:num[pos]); 41 LL sum = 0; 42 for (int i=0; i<=mnum; ++i) { 43 int npre = (pre * 10 + i) % maxn; 44 int nlcm = ggcd(lcm, i); 45 sum += dfs(pos-1, npre, nlcm, lim&&(i==mnum)); 46 } 47 return (lim==0?dp[pos][pre][lcms[lcm]]=sum:sum); 48 } 49 50 LL solve(LL x) { 51 int len = 0; 52 while(x) { 53 num[len++] = x % 10; 54 x /= 10; 55 } 56 return dfs(len-1, 0, 1, 1); // 57 } 58 59 int main() { 60 // freopen("in.cpp", "r", stdin); 61 memset(dp, -1, sizeof(dp)); 62 getLcms(); 63 int t; 64 scanf("%d", &t); 65 while(t--) { 66 LL l, r; 67 scanf("%I64d%I64d", &l, &r); 68 LL ans = solve(r) - solve(l-1); 69 printf("%I64d\n", ans); 70 } 71 return 0; 72 }
附上大腿的代码，虽然加了两个z和zz数组这两个智障产物，有碍观瞻。但是，被有爱的注释感动了。有木有。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <map> 5 #define LL long long 6 using namespace std; 7 8 /*首先，个位数最大的公倍数是5*7*8*9=2520 ，所以，我们第二维通过取余可以压缩到2520；打表可知，0-9组成的不同的公倍数不超过55个，所以第三压缩至55*/ 9 long long state[25][2600][55];/*state[a][b][c] a:第几位 b:前a位数字代表的数对2520取余的值 c:前a位数字的公倍数，在id数组中的映射的值 */ 10 int num[25];/*都懂*/ 11 int id[2600];/*所有可能出现的公倍数的映射，比如，9是可能出现的公倍数，就让id[9]=1;依次类推*/ 12 int z[15][2600];/*z[a][b] 存储的是 a与b的公倍数的值，在程序中，a指第i位的取值，b指前i-1位的公倍数，即dfs中传入的变量lcm*/ 13 int zz[15][2600];/*zz[a][b] 存储的是 前i-1位为b 新一位为 a 得到的新的数为多少，这个和上面那个其实没什么用，只是当时没找到正确超时的点，所以加上的*/ 14 int _index=0,num2=1;/*num2为上面id那个数组的计数*/ 15 16 long long gcd(long long a,long long b) 17 { 18 return (b>0?gcd(b,a%b):a); 19 }/*求公倍数*/ 20 21 void init()/*初始化*/ 22 { 23 for(int i=1;i*i<=2520;i++) 24 { 25 if(2520%i==0) 26 { 27 id[i]=num2++; 28 if(i*i!=2520)id[2520/i]=num2++; 29 } 30 }/*初始化id，原理是，2520必定是其他可能公倍数的倍数，因为2520=9*8*7*5，1，2,3,4,6，都是5 7 8 9的因数*/ 31 for(int i=0;i<=9;i++) 32 { 33 for(int j=1;j<=2520;j++) 34 { 35 z[i][j]=(i==0?j:j*i/gcd(j,i)); 36 } 37 for(int j=0;j<=2520;j++) 38 { 39 zz[i][j]=(j*10+i)%2520; 40 } 41 }/*z zz数组初始化*/ 42 // cout<<1<<endl; 43 } 44 45 void getnum(long long x) 46 { 47 memset(num,0,sizeof(num)); 48 _index=0; 49 while(x>0) 50 { 51 num[_index++]=x%10; 52 x=x/10; 53 } 54 // cout<<num[0]<<endl; 55 } 56 57 long long dfs(int i,long long st,long long lcm,int limit)/*st 前i位代表的数 lcm 前i位数的公倍数*/ 58 { 59 if(i==-1)return st%lcm==0; 60 if(!limit&&state[i][st][id[lcm]]!=-1)return state[i][st][id[lcm]]; 61 int maxn=limit?num[i]:9; 62 //cout<<lcm<<endl; 63 long long ans=0; 64 for(int j=0;j<=maxn;j++) 65 { 66 ans+=dfs(i-1,i?zz[j][st]:st*10+j,z[j][lcm],limit&&j==maxn); 67 } 68 return limit?ans:state[i][st][id[lcm]]=ans; 69 } 70 71 long long solve(long long x) 72 { 73 getnum(x); 74 return dfs(_index-1,0,1,1); 75 } 76 77 int main() 78 { 79 freopen("codeforces55D.in.cpp","r",stdin); 80 int t; 81 long long l,r; 82 init(); 83 memset(state,-1,sizeof(state));/*这是当时超时的点，第一次写数位dp，不知道只需初始化一次，然后放到了solve里，就。。。翻车了*/ 84 while(~scanf("%d",&t)) 85 { 86 while(t--) 87 { 88 scanf("%I64d%I64d",&l,&r); 89 printf("%I64d\n",solve(r)-solve(l-1)); 90 } 91 } 92 return 0; 93 }
HDU 4352 XHXJ‘s LIS
DESC：把一个数看做字符串，那么它的最长上升子序列的长度就是这个数的power value。
问，在l 到r的区间内，power value等于k的数有多少个。
(0<L<=R<2^63-1 and 1<=K<=10)
思路：
开始我是这样的：
2^63大概是10^18，k<=10，dp[20][1200][10] //1024
dp[i][j][k]=num 表示前i位的最长递增子序列为j长度为k的数的个数为num个。
dfs(pos, stu, num, lim)时。对当前位pos尝试放1~mnum的数字d时，
比较stu和nstu = stu | (1<<d)的大小..如果nstu>stu，dfs(pos-1, nstu, num+1, newlim);
否则的话。说明新加的数使得当前序列分成了两个。进行2次dfs。
1：原来的dfs(pos-1, stu, num, newlim).
2：包括新的数的LIS序列：dfs(pos-1, newstu, newnum, newlim)；
此时的newstu:对原来的stu进行一次num[pos]+1~9的与运算，和num[pos]或运算。同时计算出newnum.
bug1：1253这样搜索到的结果是2，125 和 123，所以单纯的这样记录状态也是不行的。所以第二维的状态改为：100101表示长度为x的LIS最后一位是y，
这样的话，125遇见3就会变成123了。
bug2：本来觉得len记录下当前的LIS长度会省一些重复计算，然而，状态和len相同时，k不同时返回的结果也应该是不同的，所以这个记忆化是错的。
于是就变成了这样：
int dp[20][1200][20]; //dp[i][j][k] = x 表示前i位 LIS状态为j 长度为k的 数字个数为 x
对当前的d，检查stu如果后面没有大于d的数,就直接newstu= stu | (1<<d)。否则，找出第一个大于d的数，删掉，然后或操作（1<<d），得到newstu。
前导0：检查当前d是前导0的时候，stu不变，继续搜索。
如果当前的数字出现过了，stu也不变，继续搜索。
【因为这次大腿也间歇性老年痴呆，两个人一起卡了两天晚上的几个点。最后一个bug：dp不是long long大腿找了一个点... ...感觉这个题A的也很感人，
青岛赛站结束是不是就不会这样写题了呢。有点舍不得。】
1 //HDU 4352 2 3 #include <stdio.h> 4 #include <string.h> 5 #include <iostream> 6 #define LL long long 7 using namespace std; 8 9 int num[20]; 10 LL dp[20][1200][10]; //dp[i][j][k] = x 表示前i位 LIS状态为j 长度为k的 数字个数为 x 11 12 LL dfs(int pos, int stu, int k, int lim) { //lim==1 表示当前位有限制 13 if (pos == -1) { 14 int cnt = 0; 15 for (int i=0; i<=9; ++i) { 16 if (stu & (1<<i)) { 17 cnt++; 18 } 19 } 20 return (cnt == k); 21 } 22 if (!lim && dp[pos][stu][k] != -1) return dp[pos][stu][k]; 23 int mnum = (lim == 0 ? 9 : num[pos]); 24 LL sum = 0; 25 for (int d=0; d<=mnum; ++d) { 26 bool aft = false; 27 int tstu = stu; 28 bool pre = true; 29 if (d == 0) { 30 for (int i=1; i<=9; ++i) { 31 if (tstu & (1<<i)) pre = false; 32 } 33 if (pre) { 34 sum += dfs(pos-1, stu, k, lim&&(d==mnum)); 35 continue; 36 } 37 } 38 if (tstu & (1<<d)) { 39 sum += dfs(pos-1, stu, k, lim&&(d==mnum)); 40 continue; 41 } 42 for (int i=d+1; i<=9; ++i) { 43 if (tstu & (1<<i)) { 44 tstu = (stu ^ (1<<i)); 45 tstu |= (1<<d); 46 aft = true; 47 break; 48 } 49 } 50 if (aft==false) { // 后面没有比他大的 可以直接加上 51 tstu = (stu | (1<<d)); 52 sum += dfs(pos-1, tstu, k, lim&&(d==mnum)); 53 }else sum += dfs(pos-1, tstu, k, lim&&(d==mnum)); 54 } 55 return (lim == 0 ? dp[pos][stu][k] = sum : sum); 56 } 57 58 LL solve(LL x, int k) { 59 if (x == 0) return 0; 60 int len = 0; 61 while(x) { 62 num[len++] = x % 10; 63 x /= 10; 64 } 65 return dfs(len-1, 0, k, 1); 66 } 67 68 69 int main() { 70 // freopen("in.cpp", "r", stdin); 71 memset(dp, -1, sizeof(dp)); 72 int t; 73 scanf("%d", &t); 74 int cas = 1; 75 while(t--) { 76 LL l, r; 77 int k; 78 scanf("%lld%lld%d", &l, &r, &k); 79 LL ans = solve(r, k) - solve(l-1, k); 80 printf("Case #%d: %lld\n", cas++, ans); 81 } 82 return 0; 83 }
数位DP入门
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。