题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=3555
?题意就是简单的给定一个n求1~n所有含有49的数字
?数位dp入门题可以当作模板改。
?pos表示到pos位，pre为上一位的数字用来判断是否可以得到49，sta表示状态，无非就是如果该为是4的时候和不是4的时候，对下一位dp的影响。limit表示是否到了限制如213则百位是2则十位只能为0，1。
?这题网上都是三位的dp保存或是保存三种状态，实际上和不要62那题一样，先解出不要49再用总数减去所得值就是有49的个数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL dp[100][2];
int a[100];
LL dfs(int pos, int pre, int sta, int limit)
{if(pos == -1)return 1;if(!limit&&dp[pos][sta] != -1)return dp[pos][sta];int up = limit?a[pos]:9;LL temp = 0;for(int i = 0;i <= up;i++){if(pre == 4&&i == 9)continue;temp += dfs(pos - 1, i, i == 4, i == a[pos]&&limit);}if(!limit)dp[pos][sta] = temp;return temp;
}
LL solve(LL n)
{int pos = 0;while(n > 0){a[pos++] = n % 10;n /= 10;}return dfs(pos - 1, -1, 0, 1);
}
int main()
{int t;scanf("%d", &t);while(t--){LL n;scanf("%I64d", &n);memset(dp, -1, sizeof(dp));printf("%I64d\n", n - solve(n) + 1);}return 0;
}