题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2089
模板题 ，第一道数位DP的题目
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int d[10][2],a[10];
int DFS(int pos,int pre,int state,bool limit)
{ //搜索到第几位| 前一位是什么| 状态，也即是前一位是不是6| 记录当前位最大多少if(pos==-1) return 1;int& ans=d[pos][state];if(!limit && ans!=-1) return ans;int up=limit? a[pos] : 9;int temp=0;for(int i=0;i<=up;i++){if((pre==6&&i==2)||i==4) continue;temp+=DFS(pos-1,i,i==6,limit&&i==a[pos]);}if(!limit) ans=temp;return temp;
}
int DP(int x){int pos=0;while(x){a[pos++]=x%10;x/=10;}return DFS(pos-1,-1,0,true);
}
int main(int argc, char const *argv[])
{int n,m;while(cin>>n>>m,n+m){memset(d,-1,sizeof(d));cout<<DP(m)-DP(n-1)<<endl;}return 0;
}
下面是递推的方法：
思路来自：http://blog.csdn.net/wangyuquanliuli/article/details/13761661
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int d[10][10],digit[10];
//d[i][j] 表示有i位数字，且第一位是j的数字的 满足题意的数量
void init()
{d[0][0]=1;for(int i=1;i<=7;i++)for(int j=0;j<=9;j++)for(int k=0;k<=9;k++)if(j!=4&&!(j==6&&k==2))d[i][j]+=d[i-1][k];
}
int solve(int x) // [0,x)
{int len=0;while(x){digit[++len]=x%10;x/=10;}digit[len+1]=0;int ans=0;for(int i=len;i>=1;i--){for(int j=0;j<digit[i];j++)if(j!=4&&!(j==2&&digit[i+1]==6))ans+=d[i][j];if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))break;}return ans;
}
int main(int argc, char const *argv[])
{int n,m;init();while(cin>>n>>m,n+m)cout<<solve(m+1)-solve(n)<<endl;//由于要找[n,m],而solve函数找的范围为<n,所以传参的时候应该特别注意return 0;
}