# HDU - 3555 Bob (Digital dp)

Title Link: https://cn.vjudge.net/contest/163023#problem/D
Abstract: the number of 49 numbers in the range of 1-N is required
Problem analysis: there are three ways to do the second problem of digital dp.
The first one (I think of it):
Find out the number excluding 49 in the range of 1~n, then subtract the number excluding 49 from the total number and add one (minus one more 0)
The code is as follows:

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int data[30];
ll dp[30][2];

ll dfs(int pos, int pre, bool limit)
{
if(pos == -1) return 1;
if(!limit && dp[pos][pre == 4])
{
return dp[pos][pre == 4];
}
int up = limit ? data[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; i++)
{
if(i == 9 && pre == 4) continue;
ans += dfs(pos - 1, i, limit && i == data[pos]);
}
if(!limit) return dp[pos][pre == 4] = ans;
return ans;
}

ll solve(ll n)
{
memset(dp, 0, sizeof(dp));
int pos = 0;
while(n)
{
data[pos++] = n % 10;
n /= 10;
}
ll ans = dfs(pos - 1, -1, true);
return ans;
}

int main()
{
ll n;
int t;
scanf("%d", &t);
while(t--)
{
scanf("%lld", &n);
printf("%lld\n", n - solve(n) + 1);
}
return 0;
}```

The second method:
Suppose n is 123456. When dfs reaches 049, it is obvious that the last three bits can be placed in any number. There are 10 * 10 * 10 placement methods. This is the case of! limit. When n is 49123, we run to 49
_There are only 123 + 1 methods at the back. So as long as we mark the limit and preprocess the unlimited situation, we can easily calculate the result.

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[30][2], kind[30], n;
int data[30];

ll dfs(int pos, int pre, bool limit)
{
if(pos == -1) return 0;
if(!limit && dp[pos][pre == 4]) return dp[pos][pre == 4];
int up = limit ? data[pos] : 9;
ll ans = 0;

for(int i = 0; i <= up; i++)
{
if(pre == 4 && i == 9)
{
ans = ans + (limit ? ((n % kind[pos]) + 1) : kind[pos]);
}
else ans += dfs(pos - 1, i, limit && i == data[pos]);
}
if(!limit)
return dp[pos][pre == 4] = ans;
return ans;
}

ll solve(ll k)
{
int pos = 0;
memset(dp, 0, sizeof(dp));
while(k)
{
data[pos++] = k % 10;
k /= 10;
}

return dfs(pos - 1, -1, true);
}

int main()
{
int t, i;
kind[0] = 1;
for(i = 1; i <= 18; i++)
kind[i] = kind[i - 1] * 10;

scanf("%d", &t);
while(t--)
{
scanf("%lld", &n);
printf("%lld\n", solve(n));
}
}```

The third method:
It's the traditional digital dp. At that time, it was so bad that I couldn't think of it..

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[30][30][2], n;
int data[30];

ll dfs(int pos, int pre, bool sta, bool limit)
{
if(pos == -1 && sta) return 1;
if(pos == -1 && !sta) return 0;

if(!limit && dp[pos][pre == 4][sta]) return dp[pos][pre == 4][sta];
int up = limit ? data[pos] : 9;
ll ans = 0;

for(int i = 0; i <= up; i++)
{
if(pre == 4 && i == 9) ans += dfs(pos - 1, i, true, limit && i == data[pos]);
else ans += dfs(pos - 1, i, sta/*notesHere it is. sta,Instead of false, There was a mistake before.*/, limit && i == data[pos]);
}

if(!limit) return dp[pos][pre][sta] = ans;
return ans;
}

ll solve(ll k)
{
int pos = 0;
memset(dp, 0, sizeof(dp));
while(k)
{
data[pos++] = k % 10;
k /= 10;
}
return dfs(pos - 1, -1, false, true);
}

int main()
{
int t, i;
scanf("%d", &t);
while(t--)
{
scanf("%lld", &n);
printf("%lld\n", solve(n));
}
}
```

Added by kf on Thu, 02 Apr 2020 17:44:48 +0300