题意：求1-n里有多少人包含”49“的数字

思路：数位DP，分三种情况：到第i位没有49的情况，到第i位没有49且最高位是9的情况，到第i位有49的情况，将三种情况都考虑进去就是了

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; long long dp[30][3], n; int arr[30]; void init() { dp[0][0] = 1; dp[0][1] = dp[0][2] = 0; for (int i = 1; i < 25; i++) { dp[i][0] = dp[i-1][0]*10 - dp[i-1][1]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][1] + dp[i-1][2]*10; } } long long cal(long long n) { int len = 0; while (n) { arr[++len] = n%10; n /= 10; } arr[len+1] = 0; int flag = 0; long long ans = 0; for (int i = len; i >= 1; i--) { ans += dp[i-1][2] * arr[i]; if (flag) ans += dp[i-1][0] * arr[i]; else if (arr[i] > 4) ans += dp[i-1][1]; if (arr[i+1] == 4 && arr[i] == 9) flag = 1; } if (flag) ans++; return ans; } int main() { int t; scanf("%d", &t); init(); while (t--) { cin >> n; cout << cal(n) << endl; } return 0; }