HDU3555 Bomb 数位DP

过题率一点都不高，看着有点吓人，刚开始想不出来，网上的代码思路很相似，都是dp[i][j],一维代表位数二维代表状态，状态分三种，含49，不含49，不含49但是以9开头，从一开始我的想法跟这个就不搭边啊，后来自己沿着原来的思路继续想下去，发现也是可以的，而且感觉比分三种状态的要好理解，当然还有一种记忆化搜索的更好理解

我的思路；dp[i][j],以j开头的i位数  不含49的个数，这样预处理起来其实非常方便，三层循环，第一层代表位数，第二层第三层代表相邻两个位置上的数的情况，边界值dp[0][0]=1；预处理好以后 把输入的数分解，然后从高位到低位开始找出所有不含49 的个数，然后 题目求的是不含有的 那么答案 其实就是

n减去不含有49的个数 就是含有的了

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

ll dp[25][12];//j开头的i位数
ll num[112];

void clear() {
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(int i=1;i<=20;i++) {
		for(int j=0;j<10;j++) {
			for(int k=0;k<10;k++) {
				if(j != 4 || k != 9)
					dp[i][j] += dp[i-1][k];
			}
		}
	}
}

ll cal(ll x) {
	memset(num,0,sizeof(num));
	ll cnt = 1;
	ll tmpx = x;
	while(tmpx) {
		num[cnt++] = tmpx%10;
		tmpx /= 10;
	}
	ll ans = 0;
	for(ll i=cnt;i>=0;i--) {
		for(ll j=0;j<num[i];j++) {
			if(j != 9 || num[i+1] != 4)
				ans += dp[i][j];
		}
		if(num[i] == 9 && num[i+1] == 4)break;
	}
	return ans;
}

int main() {
	clear();
	int t;
	ll n;
	scanf("%d",&t);
	while(t--) {
		scanf("%I64d",&n);
		printf("%I64d\n",n - (cal(n+1) - cal(1)));
	}
	return EXIT_SUCCESS;
}



/*
49
100
101
1000
5000
168411
*/


/*
1
1
1
20
199
7007
*/

HDU3555 Bomb 数位DP,布布扣,bubuko.com

HDU3555 Bomb 数位DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/21041953