Bomb
Time Limit: 2000/1000 MS (
Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 7187 Accepted Submission(s): 2512
Problem Description 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
HintFrom 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",
so the answer is 15.
Author fatboy_cw@WHU
Source 2010 ACM-ICPC Multi-University Training Contest（12）――Host by WHU
Recommend zhouzeyong | We have carefully selected several similar problems for you: 3554 3556 3557 3558 3559
解题思路：
题意就是求从整数1到N中有多少个含有“49”的数？ 比如N=500，那么 "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",
so the answer is 15.
做这种数位DP的题，一开始除了暴力解决，没有一点数位DP的思路。。然后又去网上找解题报告，结果看了好多篇，完全都不知道在说什么。。。。。
后来用谷歌搜到了一篇不错的解题报告：http://www.cnblogs.com/liuxueyang/archive/2013/04/14/3020032.html
先说一下总体思路：
假设统计N=591时，那么按以下的顺序进行统计：
1~499 确定5这一位，统计的数比它小
500~589 确定9这一位 ，统计的数比它小
590 确定1这一位，统计的数比它小
最后判断一下自身是不是符合 即591
循环三次就把符合题意的数的总数全都求出来了，这就是本题的数位DP的奥妙之处.
再比如 1249
1~999
1000~1199
1200~1239
1240~1248
1249
dp[i][j] 表示长度为i的数（也就是有i位数）状态为j的数的总数有多少
本题状态有三种：
①dp[i][0]代表长度为i且不包含49的数有多少个
②dp[i][1]代表长度为i且不包含49且左边第一位（最高位）为9的数有多少个
③dp[i][2]代表长度为i且包含49的数有多少个
打表预处理，0<=i<=21（21位就够了）,主要是处理状态的转移
dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; //dp[i][0]高位随便加一个数字都可以，但是会出现49XXX的情况，要减去
dp[i][1]=dp[i-1][0]; //在不含49的情况下高位加9
dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; //在含有49的情况下高位随便加一位或者不含49但高位是9，在前面最高位加上4就可以了
贴一下统计的代码：
for(int i=len;i>=1;i--)//每次确定一位
{
ans+=dp[i-1][2]*bit[i];//低位中含有49，高位随便一个1,2,3....bit[i]都可以，bit[i]是代表有几个数字，比如bit[i]=5,那么代表有五个数字，0,1,2,3,4，比5小。
if(!has)
{
if(bit[i]>4)
ans+=dp[i-1][1];//低位中高位是9，前面加上4就可以了
}
else
ans+=(dp[i-1][0])*bit[i];//如果有49，就随便选了，比如 495的时候，有490 491 492 493 494
//上面这句话困扰了我一天多的时间。为什么不写（d[i-1][0]+dp[i-1][2]）*bit[i]呢，前面已经出现过49
//那么低位任意选择都可以，dp[i-1][0]是那些低位不出现49的，dp[i-1][2]是那些低位出现49的，按理说应该
//加上啊，BUT！！！清注意循环里面的第一句ans+=dp[i-1][2]*bit[i]; 前面已经加上了dp[i-1][2]低位有
//49的情况了，哎，欲哭无泪........
if(bit[i+1]==4&&bit[i]==9)
has=true;
}
if(has)
ans++;len为数的长度，bit[i]代表从右向左第几位（从1开始）的数字.
弄明白这个统计代码花费了太多时间
对于第i位，说长度为i比较好理解，先加上长度为i-1的所有数中包含49的数，即 ans+=dp[i-1][2]*bit[i]; 为什么乘以bit[i]呢？ 比如 bit[i]=5， 那么小于5的数有5种选择，即0,1,2,3,4 ，对于每种选择长度为i-1的数中都有dp[i-1][2]个符合题意的数，所以有 dp[i-1][2]*bit[i] ， 所以就求出了第i位比5小的所有数，对于590这个数来说，就是求出了
1~499这些数中一部分有多少符合题意的数。还有i-1位数中如果高位是9，那么第i位只要是4也可以符合题意，所以有了 if(bit[i] >4) ans += dp[i-1][1];
代码：
#include
#include
using namespace std; //dp[i][0]代表长度为i不含49的数 //dp[i][1]代表长度为i不含49且最高位为9的数 //dp[i][2]代表长度为i含有49的数 long long dp[22][3]; int bit[21]; long long n; void init() { dp[0][0]=1,dp[0][1]=0,dp[0][2]=0; for(int i=1;i<=21;i++) { dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//dp[i][0]高位随便加一个数字都可以，但是会出现49XXX的情况，要减去 dp[i][1]=dp[i-1][0];//在不含49的情况下高位加9 dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//在含有49的情况下高位随便一位或者不含49但高位是9，在前面最高位加上4就可以了 } } long long cal(long long n) { int len=0; while(n) { bit[++len]=n%10; n/=10; } long long ans=0; bit[len+1]=0; bool has=false; for(int i=len;i>=1;i--)//每次确定一位 { ans+=dp[i-1][2]*bit[i]