题意：
给定一个n，求0到n范围内不含49的数的个数
思路：
这题是最基础的数位dp，可类比hdu2089 不要62，事实上，这题比不要62更简单一些。。。
首先，还是预处理打表，用一个二维数组来保存状态，dp[i][j],表示i位的满足状态j的数的个数，j有三种状态，0：不含49的，1：不含49的，但是首位是9的数，2：含有49的数。（当然0状态包含1状态）
for(int i = 1; i <= 21; i++){dp[i][0] = dp[i - 1][0] * 10 - dp[i - 1][1]; // i位的不含49的数的个数等于i-1位不含49的数的个数前面加任意一个数字减去i-1位不含49但首位为9的数的个数（因为i-1位的不含49但首位为9的数前面放4的话就变成含49的数了，这种情况要去掉）dp[i][1] = dp[i - 1][0]; //i位的不含49但首位为9的数等于i-1位的不含49的数前面加9dp[i][2] = dp[i - 1][1] + dp[i - 1][2] * 10;//i-1位不含49但首位是9的数前面加4及i-1位的含49的数前面加任意数}然后是统计过程，和不要62那题类似，先拆分，按位枚举
LL slove(LL x)
{int len = 0;LL ans = 0;while(x){len++;a[len] = x % 10;x = x / 10;}bool flag = false;a[len + 1] = 0;for(int i = len; i >= 1; i--){ans = ans + dp[i - 1][2] * a[i]; // i-1位的含有49的数加上0~a[i] - 1if(!flag && a[i] > 4)ans += dp[i - 1][1]; //如果前面还没有49，那么如果第i位能取到的话，还得加上i-1位的不含49且首位为9的数else if(flag)ans += dp[i - 1][0] * a[i]; //如果前面已经有49了，那么后面随意if(a[i + 1] == 4 && a[i] == 9)flag = true;}return ans;
}顺便提一句，统计的时候没有把本身计算进去，所以答案应该是slove(n+1)
代码：
#include <cstdio>
#include <cstring>
#define LL long longLL dp[25][3];
LL a[25];LL slove(LL x)
{int len = 0;LL ans = 0;while(x){len++;a[len] = x % 10;x = x / 10;}bool flag = false;a[len + 1] = 0;for(int i = len; i >= 1; i--){ans = ans + dp[i - 1][2] * a[i];if(!flag && a[i] > 4)ans += dp[i - 1][1];else if(flag)ans += dp[i - 1][0] * a[i];if(a[i + 1] == 4 && a[i] == 9)flag = true;}return ans;
}int main()
{memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int i = 1; i <= 21; i++){dp[i][0] = dp[i - 1][0] * 10 - dp[i - 1][1];dp[i][1] = dp[i - 1][0];dp[i][2] = dp[i - 1][1] + dp[i - 1][2] * 10;}int T;scanf("%d", &T);while(T--){LL n;scanf("%I64d", &n);printf("%I64d\n", slove(n + 1));}return 0;
}
这里还有一种和不要62做法完全一样的方法，dp[i][j]表示i位的以j开头的不含49的数的个数。slove(n+1)统计的就是0~n之间不含49的数的个数，我们要计算的0~n之间含49的数的个数就是n+1-slove(n+1)（0~n之间有n+1个数）
代码：
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;LL dp[22][10];
LL a[22];LL slove(LL x)
{int l = 0;while(x){l++;a[l] = x % 10;x = x / 10;}//printf("%d\n", l);LL sum = 0;bool flag = false;a[l + 1] = 0;for(int i = l; i >= 1; i--){
// if(flag)
// break;for(int j = 0; j < a[i]; j++){if(!(a[i + 1] == 4 && j == 9)){sum = sum + dp[i][j];}}if(a[i] == 9 && a[i + 1] == 4)break;}return sum;
}int main()
{memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int i = 1; i <= 21; i++){for(int j = 0; j <= 9; j++){for(int k = 0; k <= 9; k++)if(!(j == 4 && k == 9))dp[i][j] += dp[i - 1][k];}}
// for(int i = 1; i <= 5; i++)
// {
// for(int j = 0; j <= 9; j++)
// printf("%d ", dp[i][j]);
// printf("\n");
// }int T;scanf("%d", &T);while(T--){LL n;scanf("%I64d", &n);printf("%I64d\n", n + 1 - slove(n + 1));}return 0;
}
还有一种做法，和上面的反一下，dp[i][j]表示i位的以j开头的含49的数的个数。。。这种做法无比麻烦。。。还莫名WA了，对拍了好多数据都是对的。。。。我也把代码贴出来，如果有人发现问题务必和我讲一讲
#include <cstdio>
#include <cstring>
#define LL unsigned long long
using namespace std;LL dp[22][10];
LL a[22];
LL s[22];LL slove(LL n)
{int l = 0;while(n){l++;a[l] = n % 10;n = n / 10;}LL sum = 0;bool flag = false;for(int i = l; i >= 1; i--){if(flag){//printf("YES\n");sum += a[i] * s[i];continue;}for(int j = 0; j < a[i]; j++){sum = sum + dp[i][j];}if(a[i] == 9 && a[i + 1] == 4){flag = true;}}return sum;
}int main()
{
// freopen("1.txt", "w", stdout);dp[2][4] = 1;LL x = 1;s[1] = 1;for(int i = 2; i <= 20; i++)s[i] = s[i - 1] * 10;for(int i = 3; i <= 20; i++){//x = x * 10;for(int j = 0; j <= 9; j ++){for(int k = 0; k <= 9; k++){dp[i][j] += dp[i - 1][k];if(j == 4 && k == 9)dp[i][j] += s[i - 1] - dp[i - 1][k];}}}int T;scanf("%d", &T);while(T--){LL n;scanf("%I64u", &n);printf("%I64u\n", slove(n + 1));}
// for(int i = 1; i <= 1000000; i++)
// {
// printf("%I64d\n", slove(i + 1));
// }return 0;
}