模闆 - 動态規劃 - 數位dp

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int a[20];
ll dp[20][20/*可能需要的狀态1*/][20/*可能需要的狀态2*/];//不同題目狀态不同
ll dfs(int pos,int state1/*可能需要的狀态1*/,int state2/*可能需要的狀态2*/,bool lead/*這一位的前面是否為零*/,bool limit/*這一位是否取值被限制（也就是上一位沒有解除限制）*/)
//不是每個題都要處理前導零
{
    //遞歸邊界，最低位是0，那麼pos==-1說明這個數枚舉完了
    if(pos==-1)
        return 1;/*這裡傳回1，表示枚舉的這個數是合法的，那麼這裡就需要在枚舉時必須每一位都要滿足題目條件，也就是說目前枚舉到pos位，一定要保證前面已經枚舉的數位是合法的。 */
    //第二個就是記憶化(在此前可能不同題目還能有一些剪枝)
    if(!limit && !lead && dp[pos][state1][state2]!=-1)
        return dp[pos][state1][state2];
    /*正常寫法都是在沒有限制的條件記憶化，這裡與下面記錄狀态對應*/
    int up=limit?a[pos]:9;//根據limit判斷枚舉的上界up
    ll ans=0;
    //開始計數
    for(int i=0;i<=up;i++)//枚舉，然後把不同情況的個數加到ans就可以了
    {
        int new_state1=???;
        int new_state2=???;
        /*
        計數的時候用continue跳過不合法的狀态，不再搜尋
        */

        //合法的狀态向下搜尋
        ans+=dfs(pos-1,new_state1,new_state2,lead && i==0,limit && i==a[pos]);//最後兩個變量傳參都是這樣寫的
    }
    //計算完，記錄狀态
    if(!limit && !lead)
        dp[pos][state1][state2]=ans;
    /*這裡對應上面的記憶化，在一定條件下時記錄，保證一緻性，當然如果限制條件不需要考慮lead，這裡就是lead就完全不用考慮了*/
    return ans;
}

ll solve(ll x)
{
    //可能需要特殊處理0或者-1
    if(x<=0)
        return ???;

    int pos=0;
    while(x)//把數位分解
    {
        a[pos++]=x%10;//編号為[0,pos)，注意數位邊界
        x/=10;
    }

    return dfs(pos-1/*從最高位開始枚舉*/,0/*可能需要的狀态1*/,0/*可能需要的狀态2*/,true,true);//剛開始最高位都是有限制并且有前導零的，顯然比最高位還要高的一位視為0嘛
}

int main()
{
    memset(dp,-1,sizeof(dp));
    //一定要初始化為-1

    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}      

其實另一種計數寫法對别的題目有一定的啟發性，需要特别注意的是，無論哪種寫法的dp結果中存的數字都是和le與ri無關的。是以在數位受限時不能取用計算過的dp值，也不能更新dp值，不受限的情況可以重複利用。

無注釋版：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int a[20];
ll dp[20][MAXS1][MAXS2];
ll dfs(int pos,int s1,int s2,bool lead,bool limit) {
    if(pos==-1) {
        return ?;
    }
    if(!limit && !lead && dp[pos][s1][s2]!=-1)
        return dp[pos][s1][s2];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0; i<=up; i++) {
        int ns1=op1(s1);
        int ns2=op2(s2);
        ans+=dfs(pos-1,ns1,ns2,lead && i==0,limit && i==a[pos]);
    }
    if(!limit && !lead)
        dp[pos][s1][s2]=ans;
    return ans;
}

ll solve(ll x) {
    if(x<=0)
        return ?;

    int pos=0;
    while(x) {
        a[pos++]=x%10;
        x/=10;
    }

    return dfs(pos-1,INITS1,INITS2,true,true);
}

int main() {
    memset(dp,-1,sizeof(dp));

    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri)) {
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}      

一個更簡單的模闆，去掉了很多奇奇怪怪的東西，比如前導0，前導0的确應該特殊考慮而不能一概而論。

int dfs(int i, int s, bool e) {
    if (i==-1) return s==target_s;
    if (!e && ~f[i][s]) return f[i][s];
    int res = 0;
    int u = e?num[i]:9;
    for (int d = first?1:0; d <= u; ++d)
        res += dfs(i-1, new_s(s, d), e&&d==u);
    return e?res:f[i][s]=res;
}      

看起來清爽多了，其中：

f為記憶化數組；

i為目前處理串的第i位（權重表示法，也即後面剩下i+1位待填數）；

s為之前數字的狀态（如果要求後面的數滿足什麼狀态，也可以再記一個目标狀态t之類，for的時候枚舉下t）；

e表示之前的數是否是上界的字首（即後面的數能否任意填）。

for循環枚舉數字時，要注意是否能枚舉0，以及0對于狀态的影響，有的題目前導0和中間的0是等價的，但有的不是，對于後者可以在dfs時再加一個狀态變量z，表示前面是否全部是前導0，也可以看是否是首位，然後外面統計時候枚舉一下位數。

注意：

不滿足區間減法性質的話，不能用solve(r)-solve(l-1)。

看了學長的部分部落格之後發現其實使用f[i][j][st]表示以j開頭的i位數滿足條件st的數的個數也是可以的。待更新。

轉載于:https://www.cnblogs.com/Yinku/p/10416210.html