HDU3555 Bomb 数位DP

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

我的DP方程：f[i][j]表示数的第i位以j开头的数含有49的个数，则状态转移方程为：

　　1.j!=4时： f[i][j]=sum{ f[i-1][k] | 0<=k<=9 }

2.j==4时：f[i][j]=sum{ f[i-1][k] | 0<=k<=9 } - f[i-1][9] + pow(10,i-2) (因为j=4时，只要i-1位为9，后面的都满足)

这样的转移方程思路比较清晰，在网上看到别人的转移方程是这样的：　　　

1.f[i][0]=10*f[i-1][0]-f[i-1][1]; 表示不含49的个数
2.f[i][1]=f[i-1][0]; 表示以9开头不含49的个数
3.f[i][2]=10*f[i-1][2]+f[i-1][1]; 表示含49的个数

的确比我的优化些，把其它不需要的状态放在一起了。

DP1：

 1 //STATUS:C++_AC_15MS_288KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 #include<map>
13 using namespace std;
14 #define LL __int64
15 #define pii pair<int,int>
16 #define Max(a,b) ((a)>(b)?(a):(b))
17 #define Min(a,b) ((a)<(b)?(a):(b))
18 #define mem(a,b) memset(a,b,sizeof(a))
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N=65,INF=0x3f3f3f3f,MOD=100000000;
22 //const double DNF=100000000000;
23 
24 LL f[N][11],d[N];
25 int T;
26 LL n;
27 
28 int main()
29 {
30  //   freopen("in.txt","r",stdin);
31     int i,j,len,num[N],k,la;
32     LL t,ans;
33     d[0]=1;
34     for(i=1;i<20;i++)d[i]=d[i-1]*10;
35     f[1][4]=1;
36     for(i=2;i<20;i++){
37         for(j=0;j<10;j++){
38             for(k=0;k<10;k++)f[i][j]+=f[i-1][k];
39             if(j==4){
40                 f[i][j]-=f[i-1][9];
41                 f[i][j]+=d[i-1];
42             }
43         }
44     }
45     scanf("%d",&T);
46     while(T--)
47     {
48         scanf("%I64d",&n);
49         len=0;ans=0;
50         do num[len++]=n%10;
51         while(n/=10);
52         for(i=len-1,la=-1;i>=0;la=num[i--]){
53             for(j=num[i]-1;j>=0;j--)
54                 ans+=f[i][j];
55             if(num[i]==9 && la==4){
56                 for(t=1,i--;i>=0;i--)
57                     t+=num[i]*d[i];
58                 ans+=t;
59             }
60         }
61 
62         printf("%I64d\n",ans);
63     }
64     return 0;
65 }

DP2：

 1 //STATUS:C++_AC_15MS_264KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 #include<map>
13 using namespace std;
14 #define LL __int64
15 #define pii pair<int,int>
16 #define Max(a,b) ((a)>(b)?(a):(b))
17 #define Min(a,b) ((a)<(b)?(a):(b))
18 #define mem(a,b) memset(a,b,sizeof(a))
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N=65,INF=0x3f3f3f3f,MOD=100000000;
22 //const double DNF=100000000000;
23 
24 LL f[N][4],d[N];
25 int T;
26 LL n;
27 
28 int main()
29 {
30  //   freopen("in.txt","r",stdin);
31     int i,j,len,num[N],k,la;
32     LL t,ans;
33     d[0]=1;
34     for(i=1;i<20;i++)d[i]=d[i-1]*10;
35     f[0][0]=10;f[0][1]=1;f[0][2]=0;
36     for(i=1;i<20;i++){
37         f[i][0]=10*f[i-1][0]-f[i-1][1];
38         f[i][1]=f[i-1][0];
39         f[i][2]=10*f[i-1][2]+f[i-1][1];
40     }
41     scanf("%d",&T);
42     while(T--)
43     {
44         scanf("%I64d",&n);
45         len=0;ans=0;
46         do num[len++]=n%10;
47         while(n/=10);
48         for(i=len-1,la=-1;i>=0;la=num[i--]){
49             if(i>0){
50                 ans+=num[i]*f[i-1][2];
51                 if(num[i]>4)ans+=f[i-1][1];
52             }
53             if(num[i]==9 && la==4){
54                 for(t=1,i--;i>=0;i--)
55                     t+=num[i]*d[i];
56                 ans+=t;
57             }
58         }
59 
60         printf("%I64d\n",ans);
61     }
62     return 0;
63 }