HDU-3555 Bomb

http://acm.hdu.edu.cn/showproblem.php?pid=3555

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input

The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample Input

3
1
50
500

Sample Output

0
1
15

题意：统计[1,n]有多少个数含有'49'。

思路：数位dp，pre记录上一个数是多少，枚举到49时分limit或!limit直接计算后边的数总数

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;

ll t,n,a[70],f[70][2];

ll fac(int x)
{
	ll ret=1;
	while(x--)ret*=10;
	return ret;
}

ll calc(int pos)
{
	ll ret=1;
	for(ll v=1,i=0;i<=pos;i++,v*=10)
	{
		ret+=a[i]*v;
	}
	return ret;
}

ll dfs(int pos,bool pre,bool limit)
{
	if(pos==-1)return 0;
	if(!limit && f[pos][pre]!=-1)return f[pos][pre];
	int up=(limit?a[pos]:9);
	ll temp=0;
	for(int i=0;i<=up;i++)
	{
		if(pre&&i==9&&!limit)temp+=fac(pos);
		else if(pre&&i==9)temp+=calc(pos-1);
		else temp+=dfs(pos-1,i==4,limit&&i==a[pos]);
	}
	if(!limit)f[pos][pre]=temp;
	return temp;
}

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

int  main()
{
//	freopen("input.in","r",stdin);
	memset(f,-1,sizeof(f));
	cin>>t;
	while(t--)
	{
		cin>>n;
		cout<<solve(n)<<endl;
	}
	return 0;
}