Problem Description The counter-terrorists found a time bomb in the
dust. But this time the terrorists improve on the time bomb. The
number sequence of the time bomb counts from 1 to N. If the current
number sequence includes the sub-sequence “49”, the power of the blast
would add one point. Now the counter-terrorist knows the number N.
They want to know the final points of the power. Can you help them?Input The first line of input consists of an integer T (1 <= T <=
10000), indicating the number of test cases. For each test case, there
will be an integer N (1 <= N <= 2^63-1) as the description.The input terminates by end of file marker.
Output For each test case, output an integer indicating the final
points of the power.
数位dp。
预处理出i位数含49、不含49、不含49且首位为9的个数，然后从高位向低位统计。
#include<cstdio>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
int a[25];
LL f[25][3];
int main()
{int T,len,i;bool flag;LL ans,n;scanf("%d",&T);f[0][0]=1;for (i=1;i<=21;i++){f[i][0]=f[i-1][0]*10-f[i-1][1];f[i][1]=f[i-1][0];f[i][2]=f[i-1][2]*10+f[i-1][1];}while (T--){cin>>n;n++;len=0;while (n){a[++len]=n%10;n/=10;}ans=0;flag=0;for (i=len;i;i--){ans+=f[i-1][2]*a[i];if (!flag){if (a[i]>4) ans+=f[i-1][1];}else ans+=f[i-1][0]*a[i];if (i<len&&a[i]==9&&a[i+1]==4) flag=1;}cout<<ans<<endl;}
}