学步园

题目：Bomb

题意：给一个数n，求出所有小于n的数中含有49的个数。

题解：

	dp[i][0] 表示以49开头的个数
	dp[i][1] 表示不含49的个数（包含9开头）
	dp[i][2] 表示不含49，以9开头
	
	第一个数位dp，开始看了网上的思路，感觉理解了敲的时候有些小细节没有注意，总不对。
	1、输入的	n++ 
	2、加以9开头的应该判	！flag	否则会跟不含49重复

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
ll n;
ll base[30][3]; 		//	0->yes 	1->no 	2->9
int num[30];
int main(){
	#ifndef in
	ios::sync_with_stdio(false);
	#endif
	base[0][0] = base[0][2] = 0;
	base[0][1] = 1;
	for(int i = 1; i < 25; i ++){
		base[i][0] = base[i-1][0]*10 + base[i-1][2];
		base[i][1] = base[i-1][1]*10 - base[i-1][2];
		base[i][2] = base[i-1][1];
	}
//	for(int i = 0; i < 10; i ++) cout << base[i][0] << ' ' << base[i][1] << ' ' << base[i][2] << endl;
	int t;
	cin >> t;
	while(t--){
		cin >> n;
		n++;
		int len = 0;
		ll ans = 0;
		memset(num, 0, sizeof(num));
		while(n){
			num[++len] = n%10;
			n /= 10;
		}
		int flag = 0;
//		for(int i = len; i >= 0; i --) cout << num[i] << ' '; cout << endl;
		for(int i = len; i >= 1; i --){
			int w = num[i];
			ans += base[i-1][0]*w;
			if( flag ) ans += base[i-1][1]*w;
			if( !flag && num[i] > 4) ans += base[i-1][2];
			if( w == 9 && num[i+1] == 4) flag = 1;
		}
		cout << ans << endl;
	}
	return 0;
}