[HDU 3555]Bomb[数位DP]

题意:

给出一个数N,求从1到N中含49的数的个数.

思路:

按位DP.

dp[i][0] i bits num including 49
dp[i][1] i bits num excluding 49 but heading with 9
dp[i][2] i bits num excluding 49

转移方程

dp[i][0] = dp[i-1][0]*10 + dp[i-1][1];
dp[i][1] = dp[i-1][2];
dp[i][2] = dp[i-1][2]*10 - dp[i-1][1];

关于00049,0049,049重复的问题:

因为是预处理,所以不代表是合法的数字,只是代表数字序列.

计算结果时,最高位也是从0开始的.只有计算最高位的时候是将不足len位的数全部算进去,循环到len位之下的时候,看似i在减小,讨论的数其实是在增加(默认第i+1位填上了原数).因此每一位计算时,最高位都应该从0开始取.

dp数组初始化的时候,dp[0][2] = 1.这个是观察出来的...只有这样i=1之后的数才能根据转移方程计算正确.就像0!=1一样,这样规定之后也是合理的.

另外,由于计算结果的时候只计入

#include 
using namespace std;
typedef long long ll;
const int MAXN = 20;
ll dp[MAXN][3];
/*
dp[i][0] i bits num including 49
dp[i][1] i bits num excluding 49 but heading with 9
dp[i][2] i bits num excluding 49
*/
int bit[MAXN];
void InitDP()
{
    dp[0][2] = 1;///初始化!T^T
    dp[0][1] = dp[0][0] = 0;
    for(int i=1;i4)   ans += dp[i-1][1];
            if(bit[i+1]==4 && bit[i]==9)    flag = 1;
        }
        printf("%I64d\n",ans);
    }
}