題目大意：如果某個數中含有49，那就叫2B數（原來好像不是這個，隨便啦).問[0,n]裡有幾個2B數，n <=2^63 - 1
解題思路：數位DP,和Hdu 3652差不多，但我感覺這題更簡單，因為記錄的狀態更少。這題我用兩種方法寫過了，其實說兩種方法也就是記憶化搜索時傳遞的參數不一樣，核心都是一樣的。
第一種：傳遞三個參數，pos，flag,limit，pos表示當前轉移到第幾位，flag有三個值（2,1,0）對應著（含有49，不含49但前位是4，前位不是4也不含49），limit表示是否有上限，比如n=1234，現在轉移到12，如果下一位選3，那麼再下一位就有上限，上限為4，如果不選3，那麼下一位就沒限制，最高位9，轉移能保證轉移到數比n小。這樣dp數組時2維的。
第二種：這種跑的略慢，但更好理解。傳遞四個參數,pos,pre,flag,limit，pos和flag的意義一樣，pre表示前一位是什麼，flag表示是否含49，轉移dp數組時3維的。
測試數據：
4
1
50
500
代碼：
[cpp]
//第一種寫法
#include <stdio.h>
#include <string.h>
#define MAX 1100
#define int64 __int64
int64 digit[30];
int64 dp[30][3],n;
int64 Dfs(int pos,int flag,int limit) {
if (pos == -1) return flag == 2;
if (!limit && dp[pos][flag] != -1)
return dp[pos][flag];
int64 sum = 0;
int end = limit ? digit[pos] : 9;
for (int i = 0; i <= end; ++i) {
int have = flag; //flag == 2 || (flag == 1 && i == 4)
if (flag == 1 && i == 9)
have = 2;
if (flag == 0 && i == 4)
have = 1;
if (flag == 1 && i != 4 && i != 9)
have = 0;
//printf("pos %d flag %d have %d i %d sum %d\n",pos,flag,have,i,sum);
sum += Dfs(pos-1,have,limit&&i==end);
}
if (!limit) dp[pos][flag] = sum;
return sum;
}
int64 Cal(int64 n) {
int pos = 0;
while (n > 0) {
digit[pos] = n % 10;
n /= 10,pos++;
}
return Dfs(pos-1,0,1);
}
int main()
{
int i,j,k,t;
scanf("%d",&t);
while (t--) {
scanf("%I64d",&n);
memset(dp,-1,sizeof(dp));
printf("%I64d\n",Cal(n));
}
}
[cpp]
//第二種寫法
#include <stdio.h>
#include <string.h>
#define MAX 1100
#define int64 __int64
int64 digit[30];
int64 dp[30][10][3],n;
int64 Dfs(int pos,int pre,int flag,int limit) {
if (pos == -1) return flag == 1;
if (!limit && dp[pos][pre][flag] != -1)
return dp[pos][pre][flag];
int64 sum = 0;
int end = limit ? digit[pos] : 9;
for (int i = 0; i <= end; ++i) {
if (pre == 4 && i == 9)
sum += Dfs(pos-1,i,1,limit && end == i);
else sum += Dfs(pos-1,i,flag,limit && end == i);
}
if (!limit) dp[pos][pre][flag] = sum;
return sum;
}
int64 Cal(int64 n) {
int pos = 0;
while (n > 0) {
digit[pos] = n % 10;
n /= 10,pos++;
}
//printf("%d\n",pos);
int64 ans = Dfs(pos-1,-1,0,1);
return ans;
}
int main()
{
int i,j,k,t;
scanf("%d",&t);
while (t--) {
scanf("%I64d",&n);
memset(dp,-1,sizeof(dp));
printf("%I64d\n",Cal(n));
}
}
