题目链接
Bomb
思路
这是一道数位DP的模板题目，可以转化成不要49，是反正写的。
具体参考我前面的不要62这篇博客。正着写也有方法。
首先DP分为两种情况。
1.先搜到49，那么后面就不用搜了，直接加上后面的答案。
2.没搜到49，继续往下搜，并且带入一个状态前一个是否是否为4.
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[50][2];
int a[50];
ll z[50]={1};
ll x,y;
ll dfs(int pos,bool is4,bool limit)
{
if(pos==-1)return 0;
if(!limit&&dp[pos][is4]!=-1)return dp[pos][is4];
int up = limit?a[pos]:9;
ll temp = 0;
for(int i=0;i<=up;i++)
{
if(i==9&&is4)
{
temp+=limit?x%z[pos]+1:z[pos];
}
else temp+=dfs(pos-1,i==4,limit&&i==a[pos]);
}
return limit?temp:dp[pos][is4]=temp;
}
ll solve()
{
int pos = 0;
while(y)
{
a[pos++]=y%10;
y/=10;
}
return dfs(pos-1,false,true);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<50;i++)
z[i]=z[i-1]*10;
memset(dp,-1,sizeof(dp));
while(n--)
{
cin>>x;
y=x;
printf("%lld\n",solve());
}
}
### 总结
做完这道题，才能算简单理解数位DP的思想吧。
同一种算法，做的题越多，理解越深刻，思维能够发散的程度越广。
|