[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一樣,這樣規定之後也是合理的.

另外,由於計算結果的時候只計入<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);
    }
}