数位dp入门题hdu-3555

题目链接

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;
}