SCOI2009windy數（數位DP)

題目：Problem 1026. – [SCOI2009]windy數

分析

• 首先輸入兩個數a, b。設對于數x，在區間[0, x]内滿足要求的數字的個數為solve(x) (solve為任意函數名)，對于a, b之間的滿足要求數字的個數為solve(b)-solve(a-1)，即在區間[a , b]内滿足要求數字的個數。
• 然後先将數字處理，放到一個數組num中。此時分兩種情況：
  1. x 為個位數時，由于沒有相鄰數字，是以任意一個數字都可以，是以個數為x+1；
  2. x不為個位數時，x的最高為num[k]，此處記為tem(随便起個名字)，然後看代碼吧。
• 然後，就需要搜尋了。參數為int lastpos, int lastnum, bool islimited, bool nonum，該函數傳回的是

  

  其中情況有分為 是否受限制 和 是否前面全為0.
• 最後最重要的就是記錄狀态，即使用記憶化搜尋。詳細說明見代碼。值得注意的是如果受限制的就不記錄。

心得：

這道題根據淺談數位DP - zbtrs - 部落格園這篇部落格寫的，算法在此基礎上做一些調整，但大同小異。

對于數位DP，目前的見解是将數當字元串處理，記錄狀态(防止重複搜尋)，狀态機，剪枝，深搜。

初學算法，還有很多東西不知道，如有不當之處，歡迎指正。

#include<iostream>
#include<string.h>
using namespace std;
long long int a,b;
int num[20],dp[20][10][2];//dp儲存狀态，[n][num][nonum] n表示第n位，num表示第n位上數字為num（0 =< num =< 9)， nonum表示第n位前有沒有數字，即是不是第n位前全是0
int dfs(int lastpos, int lastnum, bool islimited, bool nonum)//nonum 目前數字前沒有數字，即全為0
{
    if(lastpos == 1)
    {
        return 1;
    }
    if(!islimited && dp[lastpos][lastnum][nonum])
        return dp[lastpos][lastnum][nonum];
    int cnt = 0, maxn = islimited ? num[lastpos-1] : 9;
    if(nonum)
    {
        for(int i = 0; i <= maxn; i++)
        {
                cnt += dfs(lastpos - 1, i, islimited && i == maxn, nonum && i == 0);
        }
    }
    else
    {
        for(int i = 0; i <= maxn; i++)
        {
            if(i - lastnum > 1 || lastnum - i > 1)
            {
                cnt += dfs(lastpos - 1, i, islimited && i == maxn, nonum && i == 0);
            }
        }
    }
    return islimited ? cnt : dp[lastpos][lastnum][nonum] = cnt;
}
int solve(long long int x)
{
    if (x < 10)
        return x+1;
    int sum = 0;
    memset(num, 0 ,sizeof(num));
    int k = 0;
    while(x)
    {
        num[++k] = x % 10;
        x /= 10;
    }
    int tem = num[k];
    for(int i = 0; i< tem; i++)
    {
        sum += dfs(k, i, false, i == 0);
        //cout << "sum : " << sum << endl;
    }
    
    sum += dfs(k, tem, true, tem == 0);
    return sum;
}
int main()
{
    cin >> a >> b;
    // cout << "b : " << solve(b) << endl;
    // cout << "  a : " << solve(a) << endl;
    cout << solve(b) - solve(a-1) << endl;
}