学步园

题意:

给出一个数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一样,这样规定之后也是合理的.

另外,由于计算结果的时候只计入<N的数,故输入的N要++.

#include <cstdio>
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;i<MAXN;i++)
    {
        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];
    }
}
void pre(ll x,int &len)
{
    int i;
    for(i=1;x;i++)
    {
        bit[i] = x%10;
        x /= 10;
    }
    bit[i] = 0;
    len = i-1;
}

int main()
{
    int T;
    scanf("%d",&T);
    InitDP();
    while(T--)
    {
        ll x, ans = 0;
        int len;
        bool flag = 0;
        scanf("%I64d",&x);
        x++;
        pre(x,len);
        for(int i=len;i;i--)
        {
            ans += dp[i-1][0]* bit[i];
            if(flag)   ans += dp[i-1][2]* bit[i];
            if(!flag && bit[i]>4)   ans += dp[i-1][1];
            if(bit[i+1]==4 && bit[i]==9)    flag = 1;
        }
        printf("%I64d\n",ans);
    }
}