[ACM] hdu 3555 Bomb (數位DP，統計1-N中含有“49”的總數）

Bomb

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 7187 Accepted Submission(s): 2512

Problem Description The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.

Output For each test case, output an integer indicating the final points of the power.
Sample Input

3
1
50
500

Sample Output

0
1
15

HintFrom 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",
so the answer is 15. 

Author fatboy_cw@WHU
Source 2010 ACM-ICPC Multi-University Training Contest（12）——Host by WHU
Recommend zhouzeyong | We have carefully selected several similar problems for you: 3554 3556 3557 3558 3559

解題思路：

題意就是求從整數1到N中有多少個含有“49”的數？ 比如N=500，那麼 "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",
so the answer is 15.

做這種數位DP的題，一開始除了暴力解決，沒有一點數位DP的思路。。然後又去網上找解題報告，結果看了好多篇，完全都不知道在說什麼。。。。。

後來用谷歌搜到了一篇不錯的解題報告：http://www.cnblogs.com/liuxueyang/archive/2013/04/14/3020032.html

先說一下總體思路：

假設統計N=591時，那麼按以下的順序進行統計：

1~499 確定5這一位，統計的數比它小

500~589 確定9這一位 ，統計的數比它小

590 確定1這一位，統計的數比它小

最後判斷一下自身是不是符合 即591

循環三次就把符合題意的數的總數全都求出來了，這就是本題的數位DP的奧妙之處.

再比如 1249

1~999

1000~1199

1200~1239

1240~1248

1249

dp[i][j] 表示長度為i的數（也就是有i位數）狀態為j的數的總數有多少

本題狀態有三種：

①dp[i][0]代表長度為i且不包含49的數有多少個

②dp[i][1]代表長度為i且不包含49且左邊第一位（最高位）為9的數有多少個

③dp[i][2]代表長度為i且包含49的數有多少個

打表預處理，0<=i<=21（21位就夠了）,主要是處理狀態的轉移

dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; //dp[i][0]高位隨便加一個數字都可以，但是會出現49XXX的情況，要減去
dp[i][1]=dp[i-1][0]; //在不含49的情況下高位加9
dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; //在含有49的情況下高位隨便加一位或者不含49但高位是9，在前面最高位加上4就可以了

貼一下統計的代碼：

for(int i=len;i>=1;i--)//每次確定一位
    {
        ans+=dp[i-1][2]*bit[i];//低位中含有49，高位隨便一個1,2,3....bit[i]都可以，bit[i]是代表有幾個數字，比如bit[i]=5,那麼代表有五個數字，0,1,2,3,4，比5小。
        if(!has)
        {
            if(bit[i]>4)
                ans+=dp[i-1][1];//低位中高位是9，前面加上4就可以了
        }
        else
            ans+=(dp[i-1][0])*bit[i];//如果有49，就隨便選了，比如 495的時候，有490 491 492 493 494
            //上面這句話困擾了我一天多的時間。為什麼不寫（d[i-1][0]+dp[i-1][2]）*bit[i]呢，前面已經出現過49
            //那麼低位任意選擇都可以，dp[i-1][0]是那些低位不出現49的，dp[i-1][2]是那些低位出現49的，按理說應該
            //加上啊，BUT！！！清注意循環裡面的第一句ans+=dp[i-1][2]*bit[i]; 前面已經加上了dp[i-1][2]低位有
            //49的情況了，哎，欲哭無淚........
        if(bit[i+1]==4&&bit[i]==9)
           has=true;
    }
    if(has)
        ans++;

len為數的長度，bit[i]代表從右向左第幾位（從1開始）的數字.

弄明白這個統計代碼花費了太多時間

對於第i位，說長度為i比較好理解，先加上長度為i-1的所有數中包含49的數，即 ans+=dp[i-1][2]*bit[i]; 為什麼乘以bit[i]呢？ 比如 bit[i]=5， 那麼小於5的數有5種選擇，即0,1,2,3,4 ，對於每種選擇長度為i-1的數中都有dp[i-1][2]個符合題意的數，所以有 dp[i-1][2]*bit[i] ， 所以就求出了第i位比5小的所有數，對於590這個數來說，就是求出了

1~499這些數中一部分有多少符合題意的數。還有i-1位數中如果高位是9，那麼第i位只要是4也可以符合題意，所以有了 if(bit[i] >4) ans += dp[i-1][1];

代碼：

#include 
#include 
using namespace std;
//dp[i][0]代表長度為i不含49的數
//dp[i][1]代表長度為i不含49且最高位為9的數
//dp[i][2]代表長度為i含有49的數
long long dp[22][3];
int bit[21];
long long n;

void init()
{
    dp[0][0]=1,dp[0][1]=0,dp[0][2]=0;
    for(int i=1;i<=21;i++)
    {
        dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//dp[i][0]高位隨便加一個數字都可以，但是會出現49XXX的情況，要減去
        dp[i][1]=dp[i-1][0];//在不含49的情況下高位加9
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//在含有49的情況下高位隨便一位或者不含49但高位是9，在前面最高位加上4就可以了
    }
}

long long cal(long long n)
{
    int len=0;
    while(n)
    {
        bit[++len]=n%10;
        n/=10;
    }
    long long ans=0;
    bit[len+1]=0;
    bool has=false;
    for(int i=len;i>=1;i--)//每次確定一位
    {
        ans+=dp[i-1][2]*bit[i];//低位中含有49，高位隨便一個1,2,3....bit[i]都可以，bit[i]是代表有幾個數字，比如bit[i]=5,那麼代表有五個數字，0,1,2,3,4，比5小。
        if(!has)
        {
            if(bit[i]>4)
                ans+=dp[i-1][1];//低位中高位是9，前面加上4就可以了
        }
        else
            ans+=(dp[i-1][0])*bit[i];//如果有49，就隨便選了，比如 495的時候，有490 491 492 493 494
            //上面這句話困擾了我一天多的時間。為什麼不寫（d[i-1][0]+dp[i-1][2]）*bit[i]呢，前面已經出現過49
            //那麼低位任意選擇都可以，dp[i-1][0]是那些低位不出現49的，dp[i-1][2]是那些低位出現49的，按理說應該
            //加上啊，BUT！！！清注意循環裡面的第一句ans+=dp[i-1][2]*bit[i]; 前面已經加上了dp[i-1][2]低位有
            //49的情況了，哎，欲哭無淚........
        if(bit[i+1]==4&&bit[i]==9)
           has=true;
    }
    if(has)
        ans++;
    return ans;
}

//以491為例，先求出所有比400小的數中有多少符合題意的，然後4這一位確定以後，再求所有比490小，再求出所有比491小
//i=3 求出數 049 149 249 349
//i=2 求出數 449
//i=1 求出數 490

//自身包含49 所以求出數491

int main()
{
    init();
    int t;cin>>t;
    while(t--)
    {
        cin>>n;
        cout<