题目大意：给出一个数n，求0-n之间含有49的数
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3555
这是我学的第二道数位dp题了，继续努力向大牛师兄们靠近。。。
思路：dp[i][k],i表示一共有i位
dp[len][0]表示长度为len时不含49的方案数
dp[len][1]表示长度为len时不含49但最高位为9的方案数
dp[len][2]表示长度为len时含有49的方案数
状态转移方程如下：
dp[i][0]=dp[i-1][0]*10-dp[i-1][1]//dp[i-1][0]中存在一种9xxxxxxx的情况，如果第i位填4的话应该减去这一种
dp[i][1]=dp[i-1][0]//dp[i-1][0]中的方案前面加个9
dp[i][2]=dp[i-1][2]*10+dp[i-1][1]//dp[i-1][0]中的方案前面加个4
之后从高位到低位查找就好啦
#include <iostream> #include <cstdio> #include <cstring> #define ll long long using namespace std; ll dp[25][3]; int digit[25];//状态为dp[i][k],k=0表示不含49,k=1表示不含49但是最高位为9,k=2表示含有49 ll ans; bool flag; void Init() { dp[0][0]=1; for(int i=1; i<20; i++) { dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; } } ll solve(ll n) { memset(digit,0,sizeof(digit)); int k=0; while(n) { digit[++k]=n%10; n/=10; } ans=0; for(int i=k; i>=1; i--) { ans+=dp[i-1][2]*digit[i]; if(flag) { ans+=dp[i-1][0]*digit[i]; } else { if(digit[i+2]==4&&digit[i+1]==9) { flag=1; ans+=dp[i-1][0]*digit[i]; } else if(digit[i]>4) ans+=dp[i-1][1]; } } return ans; } int main() { int t; ll n; cin>>t; Init(); while(t--) { flag=0; cin>>n; cout<<solve(n+1)<<endl; } }
原文：http://www.cnblogs.com/xuxueyang/p/4363428.html