原题链接
考察:数位dp
思路:
应该是入门题,但我WA了两次....这道题直接求连续的49反而不大好求,我们反过来求不连续49的个数,然后再减去即可.
Code
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 20;
LL n,f[N][N>>1];
void init()
{
for(int i=0;i<10;i++) f[1][i] = 1;
for(int i=2;i<N;i++)
for(int j=0;j<10;j++)
for(int k=0;k<10;k++)
{
if(j==4&&k==9) continue;
f[i][j]+=f[i-1][k];
}
}
LL dp(LL n)
{
if(!n) return 1;
vector<int> v;
while(n) v.push_back(n%10),n/=10;
LL res = 0;
int last = 0;
for(int i=v.size()-1;i>=0;i--)
{
int x = v[i];
for(int j=0;j<x;j++)
res+=f[i+1][j];
if(x==9&&last==4) break;
last = x;
if(!i) res++;
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
init();
while(T--)
{
scanf("%lld",&n);
LL ans = dp(n)-1;
printf("%lld\n",n-ans);
}
return 0;
}