求(一~n)中有多少个数字包含49数字
求(1~n)中有多少个数字包含49数字
#include <bits/stdc++.h> using namespace std; int digit[20]; long long dp[20][3]; long long DFS(int pos, int have, int flag)//have 0 表示无 1 表示前一位为4 2 表示已经有49 { if(pos == -1) return have == 2; if(!flag && dp[pos][have] != -1) return dp[pos][have]; int end = flag ? digit[pos] : 9; long long ans = 0; //int nhave = have; for(int i=0; i<=end; i++) { // int nhave = have; // if(have == 1 && i != 4) // nhave = 0; // if(have == 0 && i == 4) // nhave = 1; // if(have == 1 && i == 9) // nhave = 2; int nhave = have; //if(i == 4) nhave = 1; if(have == 1) { if(i == 9) nhave = 2; else nhave = 0; } if(i == 4) nhave = 1; ans += DFS(pos-1, nhave, i == end && flag); } if(!flag) dp[pos][have] = ans; return ans; } long long Cal(int n) { int pos = 0; while(n) { digit[pos++] = n % 10; n /= 10; } return DFS(pos - 1, 0, 1); } int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int n, T; cin>>T; while(T--) { cin>>n; memset(dp, -1, sizeof(dp)); cout<<Cal(n)<<endl; } return 0; }