数位DP之小小结

给出数位DP的DFS记忆化DP模板；

因为原理比较简单，不用去构造方程，而且简洁。。

ll dfs(int pos,int cet,int sum,int flag){
   if (sum<0) return 0;
   if (pos<=0) return sum==0;
   if (!flag&&dp[pos][cet][sum]!=-1) return dp[pos][cet][sum];
       int end=flag?a[pos]:9;
   ll ret=0;
   for (int i=0;i<=end;i++)
   ret+=dfs(pos-1,cet,sum+i*(pos-cet),flag&&(end==i));
   if (!flag) dp[pos][cet][sum]=ret;
   return ret;

}

复杂度是DP方程的状态数，DP设计的好坏与DP的状态数有关。。

FLAG表示是否在边界，当不再边界时我们可以做无关后面数的操作，否则，要考虑后面的数对前面有没有影响。。

我做的几道题：

HDU 3652:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 #include<iostream>
 6 using namespace std;
 7 int a[123];
 8 int len;
 9 int dp[11][90][90][10];
10 
11 
12 int dfs(int pos,int sum,int res,int last,int flag)
13 {
14     if (pos<0) return res&&(sum==0);
15     if (!flag&&dp[pos][sum][res][last]!=-1) return dp[pos][sum][res][last];
16     int end=flag?a[pos]:9;
17     int ret=0;
18     for (int i=0;i<=end;i++)
19     ret+=dfs(pos-1,(sum*10+i)%13,res||(last==1&&i==3),i,flag&&i==end);
20     if (!flag) dp[pos][sum][res][last]=ret;
21     return ret;
22 }
23 
24 int get(int x)
25 {
26     len=0;
27     while (x){
28             a[len++]=x%10;
29             x/=10;
30     }
31     return dfs(len-1,0,0,0,1);
32 }
33 
34 int main()
35 {
36     int n;
37     memset(dp,-1,sizeof(dp));
38     while (scanf("%d",&n)!=EOF)
39     {
40         printf("%d
",get(n));
41     }
42 }

View Code

HDU 3555:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 #include<iostream>
 6 using namespace std;
 7 typedef long long ll;
 8 int a[123];
 9 int len;
10 ll dp[60][90][10];
11 
12 
13 ll dfs(int pos,int res,int last,int flag)
14 {
15     if (pos<0) return res;
16     if (!flag&&dp[pos][res][last]!=-1) return dp[pos][res][last];
17     int end=flag?a[pos]:9;
18     ll ret=0;
19     for (int i=0;i<=end;i++)
20     ret+=dfs(pos-1,res||(last==4&&i==9),i,flag&&i==end);
21     if (!flag) dp[pos][res][last]=ret;
22     return ret;
23 }
24 
25 ll get(ll x)
26 {
27     len=0;
28     while (x){
29             a[len++]=x%10;
30             x/=10;
31     }
32     return dfs(len-1,0,0,1);
33 }
34 
35 int main()
36 {
37     ll n;
38     int T;
39     scanf("%d",&T);
40     memset(dp,-1,sizeof(dp));
41     while (T--)
42     {
43         scanf("%I64d",&n);
44         printf("%I64d
",get(n));
45     }
46 }

View Code

HDU 4389:有打表方法；每个100000个数打表，再统计；

数位DP代码:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 typedef long long ll;
 6 #define mod 2520
 7 int inx[22456];
 8 ll dp[20][50][2522];
 9 int a[1234];
10 using namespace std;
11 
12 void init(){
13     int num=0;
14     for (int i=1;i<=mod;i++)
15     if (mod%i==0) inx[i]=++num;
16 }
17 
18 int gcd(int a,int b){
19     if (a%b==0) return b;
20     return gcd(b,a%b);
21 }
22 
23 int lcm(int a,int b){
24     return a*b/gcd(a,b);
25 }
26 
27 ll dfs(int pos,int slcm,int sum,int flag){
28    if (pos<0) return sum%slcm==0;
29    if (!flag&&dp[pos][inx[slcm]][sum]!=-1) return dp[pos][inx[slcm]][sum];
30    int end=flag?a[pos]:9;
31    ll ret=0;
32    for (int i=0;i<=end;i++){
33    int nowlcm=slcm;
34    int nowsum=(sum*10+i) %mod;
35    if (i) nowlcm=lcm(nowlcm,i);
36    ret+=dfs(pos-1,nowlcm,nowsum,flag&&i==end);
37    }
38    if (!flag) dp[pos][inx[slcm]][sum]=ret;
39    return ret;
40 }
41 
42 ll get(ll x)
43 {
44     int pos=0;
45     while (x)
46     {
47      a[pos++]=x%10;
48      x/=10;
49     }
50     return dfs(pos-1,1,0,1);
51 }
52 
53 int main(){
54     int T;
55     scanf("%d",&T);
56     memset(dp,-1,sizeof(dp));
57     init();
58     while (T--){
59         ll a,b;
60         scanf("%I64d%I64d",&a,&b);
61         printf("%I64d
",get(b)-get(a-1));
62     }
63     return 0;
64 }

View Code

这里我们不可能保存每个值去除以其数位的和，我们可以枚举数位的和，然后DFS能满足的数的个数，再看其数能不能整除其数位。

数位和的状态是1-81。。。；

HDU 4334 :

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<math.h>
 4 #include<string.h>
 5 #include<algorithm>
 6 
 7 using namespace std;
 8 int bit[234];
 9 int dp[20480][20];
10 
11 int dfs(int t,int num,int flag)
12 {
13     if (t==0) return num>=0;
14     if (num<0) return 0;
15     if (!flag&&dp[num][t]!=-1) return dp[num][t];
16     int ans=0;
17     int  end=flag?bit[t]:9;
18     for (int i=0;i<=end;i++)
19          ans+=dfs(t-1,num-i*(1<<(t-1)),flag&&i==end);
20     if (!flag) dp[num][t]=ans;
21     return ans;
22 }
23 int main()
24 {
25     int T;
26     scanf("%d",&T);
27     memset(dp,-1,sizeof(dp));
28     for (int i=1;i<=T;i++)
29     {
30         int a,b;
31         scanf("%d%d",&a,&b);
32         int t=0;
33         int  ans=0;
34         while (a)
35         {
36             ans+=a%10*(1<<t);
37             t++;
38             a/=10;
39         }
40         int len=0;
41         while (b)
42         {
43             bit[++len]=b%10;
44             b/=10;
45         }
46         printf("Case #%d: %d
",i,dfs(len,ans,1));
47     }
48     return 0;
49 }

View Code

前面的做了差不多，这也是简单题了，先预处理F[A],然后处理。。

codeforces 55D: http://codeforces.com/problemset/problem/55/D

比较麻烦的题；求一个范围的书能被其数位整除的个数。

切题点：1-9的公倍数为2520;

我们可以定义方程DP[POS][LCM][SUM]表示：处理第POS位，其数位的最小公倍数数多少，该数MOD2520是多少，但是有个问题会爆内存，

要开DP[20][2520][2520];

解决办法是：2520=2^3*3^2*5*7

y于是又4*3*2*2= 48中组合。。

我们可以对LCM用下标代替，就不会爆内存了。。。真是奇妙的方法。。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 typedef long long ll;
 6 #define mod 2520
 7 int inx[22456];
 8 ll dp[20][50][2522];
 9 int a[1234];
10 using namespace std;
11 
12 void init(){
13     int num=0;
14     for (int i=1;i<=mod;i++)
15     if (mod%i==0) inx[i]=++num;
16 }
17 
18 int gcd(int a,int b){
19     if (a%b==0) return b;
20     return gcd(b,a%b);
21 }
22 
23 int lcm(int a,int b){
24     return a*b/gcd(a,b);
25 }
26 
27 ll dfs(int pos,int slcm,int sum,int flag){
28    if (pos<0) return sum%slcm==0;
29    if (!flag&&dp[pos][inx[slcm]][sum]!=-1) return dp[pos][inx[slcm]][sum];
30    int end=flag?a[pos]:9;
31    ll ret=0;
32    for (int i=0;i<=end;i++){
33    int nowlcm=slcm;
34    int nowsum=(sum*10+i) %mod;
35    if (i) nowlcm=lcm(nowlcm,i);
36    ret+=dfs(pos-1,nowlcm,nowsum,flag&&i==end);
37    }
38    if (!flag) dp[pos][inx[slcm]][sum]=ret;
39    return ret;
40 }
41 
42 ll get(ll x)
43 {
44     int pos=0;
45     while (x)
46     {
47      a[pos++]=x%10;
48      x/=10;
49     }
50     return dfs(pos-1,1,0,1);
51 }
52 
53 int main(){
54     int T;
55     scanf("%d",&T);
56     memset(dp,-1,sizeof(dp));
57     init();
58     while (T--){
59         ll a,b;
60         scanf("%I64d%I64d",&a,&b);
61         printf("%I64d
",get(b)-get(a-1));
62     }
63     return 0;
64 }

View Code

FZU 2113:

OJ挂了，现在也没评测出来。。

求一个范围[L,R]数中1的总数。。

方程想到就是超级大水题；

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<cmath>
typedef long long ll;
int a[123];
ll dp[123][123];
using namespace std;


ll dfs(int pos,int num,int flag)
{
    if (pos<0) return num;
    if (!flag&&dp[pos][num]!=-1) return dp[pos][num];
    int end=flag?a[pos]:9;
    ll ret=0;
    for (int i=0;i<=end;i++)
        if (i==1) ret+=dfs(pos-1,num+1,flag&&end==i);
        else ret+=dfs(pos-1,num,flag&&end==i);
    if (!flag) dp[pos][num]=ret;
    return ret;
}

ll get(ll x)
{
    int pos=0;
    while (x){
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos,0,1);
}

int main()
{
    ll a,b;
    memset(dp,-1,sizeof(dp));
    while (scanf("%lld%lld",&a,&b)!=EOF){
          printf("%lld
",get(b)-get(a-1));
    }
    return 0;
}

View Code

还有好多好多各种状态的数位DP题，果然太弱切不动。。