數位dp

我從就只用記憶化寫數位dp, 隨便寫寫, 因為某天突然不會寫了

首先數位dp一般會把 \([l,r]\) 拆成 \([1,r]\) 和 \([1,l-1]\) , 因為不管你問同一個數什么問題, 它的答案一定都是一樣的, 我們之后就不提這個事了

怎么dp? 我不會, 我不會, 我不會

但是搜索簡單, 我們寫記憶化(致敬我有關變量在外邊的錯誤記憶化)

我們那一道題做例子

P4999 煩人的數學作業

題意: [l,r] 每個數的數位和

正常的爆搜, 一位一位填數誰都會, 我們考慮如何把兩個一模一樣的結構給挖出來, 也就是我們需要記錄什么

首先是解決問題必須的, 當前填到哪一位, 數位到現在加到多少

其次我們考慮對于一個情況, 怎么保證搜索樹中一個情況的子樹完全相同

我們在處理 [1,114514] 時, 假設我們在添第四位, 如果第三為添的是 \(4\) , 我們在第四位便不可以添超過 \(5\) 的數字, 若沒有則可以從 \(0\) 填到 \(9\) , 我們需要記錄當前位置有沒有限制, 這個是所有數位dp都需要的

關于前導零, 這個問題求的是和, 所以不用考慮, 但做題的時候記得研究會不會造成不同

這樣我們就在搜索樹中, 一模一樣的子樹我們只需要計算一次, 大大加速了我們的算法

具體到代碼中看一看吧

\(dfs\) 函數

int dfs(int pos, bool limit, int sum){
    if(!pos) return sum;//如果填完就返回當前值
    if(!limit&&dp[pos][sum]) return dp[pos][sum]; //若有搜索過一模一樣的返回搜過的值
    int up=(limit?a[pos]:9), res=0;//確定枚舉填數的上限
    for(int i=0; i<=up; ++i){
        res=(res+dfs(pos-1,i==up&&limit, sum+i))%mod;//直接繼續, limit和sum繼承當前
    }
    if(!limit) dp[pos][sum]=res%mod;//保存子樹
    return res%mod;//返回
}

其實我們同樣可以將我們的 \(limit\) 記作 \(dp\) 中的一維, 只是記錄沒什么大用罷了

之后放一下整體代碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[20][10000];
const int mod=1e9+7;
int a[20], len;
int dfs(int pos, bool limit, int sum){
    if(!pos) return sum;
    if(!limit&&dp[pos][sum]) return dp[pos][sum];
    int up=(limit?a[pos]:9), res=0;
    for(int i=0; i<=up; ++i){
        res=(res+dfs(pos-1,i==up&&limit, sum+i))%mod;
    }
    if(!limit) dp[pos][sum]=res%mod;
    return res%mod;
}
int solve(int x){
    len=0;
    while(x>0){//分解數字
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,true,0)%mod;
}
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin>>T;
    while(T--){
        int l, r; cin>>l>>r;
        cout<<(solve(r)-solve(l-1)+mod)%mod<<'\n';
    }
    return 0;
}

P2602 數字計數

給定兩個正整數 a 和 b，求在 [a,b] 中的所有整數中，每個數碼(digit)各出現了多少次。

這個需要考慮前導零了, 填到 00_ 的時候如果填 \(0\) 總不能記一個貢獻吧

其實記搜寫這個都大差不差

\(dfs\) 函數

int dfs(int pos, bool limit, bool lead, int sum){
	if(!pos) return sum;
	if(!limit&&!lead&&dp[pos][sum][digit!=0]!=-1) return dp[pos][sum][digit!=0];//0與其他不同,受到前導零的影響
	int res=0, up=limit?a[pos]:9;
	for(int i=0; i<=up; ++i){
		int tmp=sum+(i==digit);
		if(lead&&digit==0&&i==0) tmp=0; //就是剛剛提到的情況
		res+=dfs(pos-1,limit&&i==up,lead&&i==0,tmp);
	}
	if(!limit&&!lead) dp[pos][sum][digit!=0]=res;
	return res;
}

想必也容易看懂

直接放代碼↓

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=100;
int dp[MN][MN*MN][2];
int a[MN], len, digit;
int dfs(int pos, bool limit, bool lead, int sum){
	if(!pos) return sum;
	if(!limit&&!lead&&dp[pos][sum][digit!=0]!=-1) return dp[pos][sum][digit!=0];
	int res=0, up=limit?a[pos]:9;
	for(int i=0; i<=up; ++i){
		int tmp=sum+(i==digit);
		if(lead&&digit==0&&i==0) tmp=0;
		res+=dfs(pos-1,limit&&i==up,lead&&i==0,tmp);
	}
	if(!limit&&!lead) dp[pos][sum][digit!=0]=res;
	return res;
}
int cnt[10];
void solve(int x, int opt){
	len=0; while(x){
		a[++len]=x%10; x/=10;
	}
	for(int i=0; i<=9; ++i){
		digit=i; int res=dfs(len,1,1,0);
		cnt[i]+=opt*res;
	}
}
int l, r;
signed main(){
	memset(dp,-1,sizeof(dp));
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>l>>r;
	solve(r,1); solve(l-1,-1);
	for(int i=0; i<=9; ++i) cout<<cnt[i]<<" ";

	return 0;
}

用記憶化寫數位dp, 我們可以直接套用這個模式走

dfs函數:

• 填完返回貢獻
• 返回相同情況
• 確定枚舉上限
• 進行下一步搜索
• 記錄當前情況的值

所以這個沒什么需要講的, 真正搞明白一個, 其他的就很好懂了

下邊放點題, 沒啥好說的, 就說說dfs的細節, 然后給代碼了

題目

P6218 # [USACO06NOV] Round Numbers S

如果一個正整數的二進制表示中，0 的數目不小于 1 的數目，那么它就被稱為「圓數」。

例如，9 的二進制表示為 1001，其中有 2 個 0 與 2 個 1。因此，9 是一個「圓數」。

請你計算，區間 [l,r] 中有多少個「圓數」。

我們按照二進制拆數, 肯定需要考慮前導零, 記錄 \(0\) 和 \(1\) 的數量, 直接套板子

代碼↓

#include <bits/stdc++.h>
using namespace std;
const int MN=1e2+114;
int dp[MN][MN][MN], a[MN];
int dfs(int pos, bool limit, bool lead, int zero, int one){
    if(!pos) return zero>=one;
    if(!lead&&!limit&&dp[pos][zero][one]) return dp[pos][zero][one];
    int res=0, up=limit?a[pos]:1;
    for(int i=0; i<=up; ++i){
        if(lead&&i==0)
            res+=dfs(pos-1,limit&&i==up,1,zero,one);
        else
            res+=dfs(pos-1,limit&&i==up,0,zero+(i==0),one+(i==1));
    }
    if(!lead&&!limit) dp[pos][zero][one]=res;
    return res;
}
int solve(int x){
    int len=0;
    while(x){
        a[++len]=x%2;
        x/=2;
    }
    return dfs(len,1,1,0,0);
}
int main(){
    int l, r;
    cin>>l>>r;
    cout<<solve(r)-solve(l-1);
    return 0;
}

P2657 Windy數

不含前導零且相鄰兩個數字之差至少為 2 的正整數被稱為 windy 數。windy 想知道，在 a 和 b 之間，包括 a 和 b ，總共有多少個 windy 數？

每一次填數合法僅與上一個數有關, 記錄上一個數字, 考慮前導零, 套板子

代碼↓

#include <iostream>
#define int long long
using namespace std;
int A, B; const int MN=40;
int a[MN];
int dp[MN][MN];
int dfs(int pos, bool limit, bool lead, int last){
	if(!pos) return 1;
	if(!limit&&!lead&&dp[pos][last]) return dp[pos][last];
	int up=limit?a[pos]:9, res=0;
	for(int i=0; i<=up; ++i){
		if(lead&&i==0) res+=dfs(pos-1,limit&&i==up, 1, 0);
		else if(lead||abs(last-i)>=2) res+=dfs(pos-1,limit&&i==up, 0, i);
	}if(!limit&&!lead) dp[pos][last]=res;
	return res;
}
int solve(int x){
	int len=0;
	while(x){
		a[++len]=x%10; x/=10;
	}
	return dfs(len,1,1,0);
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>A>>B;
	cout<<solve(B)-solve(A-1); return 0;
}