hdoj 3555 BOMB(数位dp)

//hdoj 3555

//2013-06-27-16.53

#include <stdio.h>

#include <string.h>

__int64 dp[21][3], n;

int len, bit[21];

//dp[i][0] 长度为i 包含49的个数

//dp[i][1] 长度为i没有49但以9开头的

//dp[i][2] 长度为i 没有49

void init()

{

    dp[0][2] = 1;

    for (int i = 1; i < 20; i++)

    {

        dp[i][0] = (__int64)dp[i-1][0]*10 + dp[i-1][1];

        dp[i][1] = dp[i-1][2];

        dp[i][2] = (__int64) dp[i-1][2]*10 - dp[i-1][1];

    }

}

int main()

{

    init();

    int t;

    scanf("%d", &t);

    while (t--)

    {

        scanf("%I64d", &n);

        len = 0;

        n++;

        while (n)

        {

            bit[++len] = n%10;

            n /= 10;

        }

        bit[len+1] = 0;

        __int64 ans = 0;

        bool flag = false;

        for (int i = len; i; i--)

        {

            ans += (__int64)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] == 9 && bit[i+1] == 4)

                flag = true;

        }

        printf("%I64d\n", ans);

    }

    return 0;

}
巴特西

hdoj 3555 BOMB(数位dp)

最新文章

热门文章
