学步园

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

题意就是找0到n有多少个数中含有49。数据范围接近10^20

DP的状态是2维的dp[len][3]
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];  // not include 49  如果不含49且，在前面可以填上0-9 但是要减去dp[i-1][1]
因为4会和9构成49
dp[i][1] = dp[i-1][0];  // not include 49 but starts with 9  这个直接在不含49的数上填个9就行了
dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; // include 49  已经含有49的数可以填0-9，或者9开头的填4

接着就是从高位开始统计

在统计到某一位的时候，加上 dp[i-1][2] * digit[i] 是显然对的，因为这一位可以填 0 - (digit[i]-1)
若这一位之前挨着49，那么加上 dp[i-1][0] * digit[i] 也是显然对的。
若这一位之前没有挨着49，但是digit[i]比4大，那么当这一位填4的时候，就得加上dp[i-1][1]

#include <iostream>
#include <string.h>
using namespace std;


int dp[20][3]; //状态转移数组
__int64 N; //上界N
int digit[20];

int main() {

	memset(dp, 0 ,sizeof(dp));


	dp[0][0] = 1;
	//先构造状态转移数组 dp[3][0]=980  可以理解为在 0-1000之间(3位数)，不包含49的数有980个
	for(int i=1; i<20; i++){
		// 如果不含49且，在前面可以填上0-9 但是要减去dp[i-1][1] 因为4会和9构成49
		dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];
		// not include 49 but starts with 9  这个直接在不含49的数上填个9就行了
		dp[i][1] = dp[i-1][0];
		// include 49  已经含有49的数可以填0-9，或者9开头的填4
		dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1];
	}
	int t;
	cin >> t;
	while(t--){
		int len=0,last=0; //位数，临时变量
		long long ans = 0; //最后的答案
		unsigned long long n =0;
		cin >> n;
		n ++; //枚举上界
		memset(digit, 0, sizeof(digit));
		while(n)
		{
			digit[++len] = n % 10;
			n /= 10;
		}
		bool flag = false;
		for(int i=len; i>=1; i--){
			ans += dp[i-1][2] * digit[i]; //例：对于一个3位数 5xx, 即(dp[2][2]) * 5
			if(flag)
				ans += dp[i-1][0] * digit[i]; //例：493xxx, 如果高位已有49， 后面所有的都要算上
			else if(!flag && digit[i] > 4){ //如果高位比4大，即会出现49
				ans += dp[i-1][1];

			if(last == 4 && digit[i] == 9)
				flag = true;
			last = digit[i];
		}

	}

		cout << ans << endl;
	}
	return 0;
}