HDU3555-数位DP

//数位DP
//从最高位开始向下DP#include<stdio.h>#include<iostream>#include<string.h>using namespace std ;int bit[40] ;long long dp[40][3] ;
//dp[len][0] 代表数字长度为len不含49的个数
//dp[len][1] 代表数字长度为len不含49但是以9开头的个数（显然dp[len][1]包含在dp[len][0]中）
//dp[len][2] 代表数字长度为len含有49的个数void Init(){memset(dp , 0 , sizeof(dp)) ;dp[0][0] = 1 ;for(int i = 1 ; i <= 22 ; 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][2] * 10 + dp[i-1][1] ;}}long long solve(long long n){long long temp = n ;int len = 0 ;while(n != 0){bit[++ len] = n % 10 ;n /= 10 ;}bit[len + 1] = 0 ;long long sum = 0 ;int flag = 0 ;for(int i = len ; i >= 1 ; i --){sum += bit[i] * dp[i-1][2] ;if(flag) sum += bit[i] * dp[i-1][0] ;//当前已经有49，则后面的处理任意