感觉数位DP用记忆化搜索挺简单的。
数位DP记忆化搜索模板
ll n, a[maxn];
ll dp[maxn][state]; //代表当前到了第 pos 位,某种状态 state 时的答案,state可以为多个状态。
ll dfs(int pos, int state, bool lead, bool limit) { //pos,state 同上,lead 代表是否有前导0,limit 代表是否可以取到原数。
if(pos == 0) return 1; //所有数位搜索完成
if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state]; //记忆化
int up;
if(!limit) up = 9; //这一位可以取 0~9
else up = a[pos]; //否则不能超过要求数位
ll ans = 0;
for(int i = 0;i <= up;i++) {
特殊判断;
ans += dfs(pos-1, state, (lead == true && i == 0),(limit == true && i == a[pos]));//这里的 state 是更新后的 state。
}
}
ll solve(ll x) {
memset(dp, -1, sizeof(dp));
int top = 0;
while(x != 0) {
a[++top] = x % 10;
x /= 10;
}
return dfs(top, state, true, true);
}
题目
P2657 [SCOI2009]windy数
$dp[pos][state]$ 表示当前位为 $pos$,$pos+1$ 位选择 $state$,然后和当前位的选择判断即可。
const int maxn = 15;
ll a[maxn];
ll dp[maxn][10];
ll dfs(int pos, int state, bool lead, bool limit) {
if(pos == 0) return 1;
if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
int up;
if(!limit) up = 9;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++) {
if(abs(i - state) < 2) continue;
if(lead == true && i == 0) ans += dfs(pos-1, -2, true, (limit == true && i == a[pos]));
else ans += dfs(pos-1, i, false, (limit == true && i == a[pos]));
}
if(!limit && !lead)
dp[pos][state] = ans;
return ans;
}
ll solve(ll x) {
memset(dp, -1, sizeof(dp));
int top = 0;
while(x != 0) {
a[++top] = x % 10;
x /= 10;
}
return dfs(top, -2, true, true);
}
P4124 [CQOI2016]手机号码
$dp[pos][num1][num2][used4][used8][triple]$ 表示当前位为 $pos$,$pos+1$ 位为 $num1$,$pos+2$ 位为 $num2$,是否有$4$,是否有$8$,是否有三位连续的数。
const int maxn = 20;
ll a[maxn];
ll dp[maxn][10][10][2][2][2];
ll dfs(int pos, int num1, int num2, bool used4, bool used8, bool triple, bool lead, bool limit) {
if(pos == 0) return triple;
if(!limit && !lead && dp[pos][num1][num2][used4][used8][triple] != -1) return dp[pos][num1][num2][used4][used8][triple];
int up;
if(!limit) up = 9;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++) {
if(used4 == true && i == 8) continue;
if(used8 == true && i == 4) continue;
if(lead == true && i == 0) ans += dfs(pos - 1, 0, -1, used4, used8, triple, true, (limit == true && i == a[pos]));
else ans += dfs(pos-1, i, num1, (used4 == true || i == 4), (used8 == true || i == 8), (triple == true || (i == num1 && i == num2)), false, (limit == true && i == a[pos]));
}
if(!limit && !lead)
dp[pos][num1][num2][used4][used8][triple] = ans;
return ans;
}
ll solve(ll x) {
memset(dp, -1, sizeof(dp));
int top = 0;
while(x != 0) {
a[++top] = x % 10;
x /= 10;
}
return dfs(top, 0, -1, false, false, false, true, true);
}
P2602 [ZJOI2010]数字计数
本来我的状态为 $dp[pos]$ 表示当前位为 $pos$,含有查找数位的数量。
但是在记忆化时有一个问题
假设我要去找$1$的个数
例如$11110…$,$10234…$这两个数都已经搜了$5$位,则这两个数的状态都是一样的,但很明显前者$1$的数量要比后者的多,所以这个状态不对。
那么怎么才是对的呢?
发现 $11000…$,$12410…$这两个数当前$1$的个数一样,而最后总共$1$的个数应该也是一样的
那么状态定义 $dp[pos][cnt]$ 表示当前位 $pos$,含有 $cnt$ 个查找数位的数量。
const int maxn = 15;
ll a[maxn];
ll dp[maxn][maxn];
ll dfs(int pos, int key, ll cnt, bool lead, bool limit) {
if(pos == 0) return cnt;
if(!lead && !limit && dp[pos][cnt] != -1) return dp[pos][cnt];
int up;
if(!limit) up = 9;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++) {
if(lead == true && i == 0) ans += dfs(pos-1, key, cnt, true, (limit == true && i == a[pos]));
else ans += dfs(pos-1, key, cnt + (i == key), false, (limit == true && i == a[pos]));
}
if(!lead && !limit)
dp[pos][cnt] = ans;
return ans;
}
ll solve(ll x,int key) {
memset(dp, -1, sizeof(dp));
int top = 0;
while(x != 0) {
a[++top] = x % 10;
x /= 10;
}
return dfs(top, key, 0, true, true);
}
P3286 [SCOI2014]方伯伯的商场之旅
梁伯伯
借用老师的题解:
const int maxn = 50;
const int maxsum = 4000;
ll k, a[maxn];
ll dp[maxn][maxsum];
ll dfs1(int pos, ll sum, bool lead, bool limit) {
if(pos == 0) return sum;
if(!limit && !lead && dp[pos][sum]!=-1) return dp[pos][sum];
int up;
if(!limit) up = k - 1;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++) {
if(lead == true && i == 0) ans += dfs1(pos-1, sum, true, (limit == true && i == a[pos]));
else ans += dfs1(pos-1, sum + i * (pos - 1), false, (limit == true && i == a[pos]));
}
if(!limit && !lead)
dp[pos][sum] = ans;
return ans;
}
ll dfs2(int pos, ll state, bool lead, bool limit, int key) {
if(state < 0) return 0;
if(pos == 0) return state;
if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
int up;
if(!limit) up = k - 1;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++) {
if(lead == true && i == 0) ans += dfs2(pos-1, state, true, (limit == true && i == a[pos]), key);
else if(pos >= key) ans += dfs2(pos - 1, state + i, false, (limit == true && i == a[pos]), key);
else ans += dfs2(pos - 1, state - i, false, (limit == true && i == a[pos]), key);
}
if(!limit && !lead)
dp[pos][state] = ans;
return ans;
}
ll solve(ll x) {
memset(dp, -1, sizeof(dp));
int top = 0;
while(x != 0) {
a[++top] = x % k;
x /= k;
}
ll ans = dfs1(top, 0, true, true);
for(int i = 2;i <= top;i++) {
memset(dp, -1, sizeof(dp));
ans -= dfs2(top, 0, true, true, i);
}
return ans;
}
P4317 花神的数论题
双倍经验题。
状态同 P2602 [ZJOI2010]数字计数。
const int maxn = 50;
ll a[maxn];
ll dp[maxn][maxn];
ll dfs(int pos, ll cnt, bool lead, bool limit) {
if(pos == 0) return max(cnt, 1);
if(!limit && !lead && dp[pos][cnt] != -1) return dp[pos][cnt];
int up;
if(!limit) up = 1;
else up = a[pos];
ll ans = 1;
for(int i = 0;i <= up;i++) {
if(lead == true && i == 0) ans = (ans * dfs(pos - 1, cnt, true, (limit == true && i == a[pos]))) % Mod;
else ans = (ans * dfs(pos - 1, cnt + i, false, (limit == true && i == a[pos]))) % Mod;
}
if(!limit && !lead)
dp[pos][cnt] = ans;
return ans;
}
ll solve(ll x) {
memset(dp, -1, sizeof(dp));
int top = 0;
while(x != 0) {
a[++top] = x % 2;
x /= 2;
}
return dfs(top, 0, true, true);
}
P4999 烦人的数学作业
思路同 P2602 [ZJOI2010]数字计数。
设状态 $dp[pos][sum]$ 表示当前位为 $pos$,数字和为 $sum$ 的答案。
const int maxn = 20+5;
const int maxsum = 200+5;
ll a[maxn];
ll dp[maxn][maxsum];
ll dfs(int pos, int sum, bool lead, bool limit) {
if(pos == 0) return sum;
if(!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
int up;
if(!limit) up = 9;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++)
ans = (ans + dfs(pos - 1, sum + i, (lead == true && i == 0), (limit == true && i == a[pos]))) % Mod;
if(!limit && !lead)
dp[pos][sum] = ans;
return ans;
}
ll solve(ll x) {
memset(dp, -1, sizeof(dp));
int top = 0;
while(x != 0) {
a[++top] = x % 10;
x /= 10;
}
return dfs(top, 0, true, true);
}
T180087 花式打牌
这题我想吐槽一下,比赛的时候一直在想容斥,结果喜提$0$分qwq
但如果将每种牌选出的数量当做一个数位,发现可以用数位 dp
考虑分 $\text{op}$ 去写。
$\text{op}=1$,状态 $dp[pos][rest][ok]$ 表示当前位为 $pos$,剩余 $rest$ 张,是否有炸弹。
$\text{op}=2$,状态 $dp[pos][rest][last][ok]$ 表示当前位为 $pos$,剩余 $rest$ 张,$pos+1$ 位为 $last$,是否有飞机。
$\text{op}=3$,发现用四维状态表示前四位的选择空间开销过大,但其实可以只用一维表示已经连续了几种牌。
$\text{op}=4$
若将状态定为 $dp[pos][rest][cnt][last][ok1][ok2][ok3]$ 表示当前位为 $pos$,剩余 $rest$ 张,已经连续了 $cnt$ 为,上一位为 $last$,是否有炸弹,是否有飞机,是否有顺子,则空间过大。
但由于最后选择中不能有飞机和顺子,所以只有出现了飞机和顺子,最后这种选择一定不符合要求。
故可省掉 $ok2$,$ok3$。
const int maxn = 1000 + 5;
const int maxk = 1500 + 5;
int dp1[maxn][maxk][2], dp2[maxn][maxk][5][2], dp3[maxn][maxk][5][2], dp4[maxn][maxk][5][5][2];
int dfs1(int pos, int rest, bool ok) {
if(rest < 0 || pos == -1) return 0;
if(rest == 0) return ok;
if(dp1[pos][rest][ok] != -1) return dp1[pos][rest][ok];
int ans = 0;
for(int i = 0;i <= 4;i++)
ans = (ans + dfs1(pos - 1, rest - i, (ok == true || i == 4))) % Mod;
dp1[pos][rest][ok] = ans;
return ans;
}
int dfs2(int pos, int rest, int last, bool ok) {
if(rest < 0 || pos == -1) return 0;
if(rest == 0) return !ok;
if(dp2[pos][rest][last][ok] != -1) return dp2[pos][rest][last][ok];
int ans = 0;
for(int i = 0;i <= 4;i++)
ans = (ans + dfs2(pos - 1, rest - i, i, (ok == true || (i >= 3 && last >= 3)))) % Mod;
dp2[pos][rest][last][ok] = ans;
return ans;
}
int dfs3(int pos, int rest, int cnt, bool ok)
{
if(rest < 0 || pos == -1) return 0;
if(rest == 0) return !ok;
if(dp3[pos][rest][cnt][ok] != -1) return dp3[pos][rest][cnt][ok];
int ans = 0;
for(int i = 0;i <= 4;i++) {
int k = (i >= 1) ? 1 : -cnt;
ans = (ans + dfs3(pos - 1, rest - i, cnt + k, (ok == true || cnt + k >=5))) % Mod;
}
dp3[pos][rest][cnt][ok] = ans;
return ans;
}
int dfs4(int pos, int rest, int cnt, int last, bool ok) {
if(rest < 0 || pos == -1) return 0;
if(rest == 0) return ok;
if(dp4[pos][rest][cnt][last][ok] != -1) return dp4[pos][rest][cnt][last][ok];
int ans = 0;
for(int i = 0;i <= 4;i++) {
int k = (i >= 1) ? 1 : -cnt;
if(!(cnt + k >= 5 || (i >= 3 && last >= 3)))
ans = (ans + dfs4(pos - 1, rest - i, cnt + k, i, (ok == true || (i == 4)))) % Mod;
}
dp4[pos][rest][cnt][last][ok]=ans;
return ans;
}
int solve(int x, int opt) {
int top = 0;
if(opt == 1) {memset(dp1, -1, sizeof(dp1)); return dfs1(x, x / 3 * 4, false);}
if(opt == 2) {memset(dp2, -1, sizeof(dp2)); return dfs2(x, x / 3 * 4, -1, false);}
if(opt == 3) {memset(dp3, -1, sizeof(dp3)); return dfs3(x, x / 3 * 4, 0, false);}
if(opt == 4) {memset(dp4, -1, sizeof(dp4)); return dfs4(x, x / 3 * 4, 0, -1, false);}
}
P3413 SAC#1 - 萌数
可以用所有数减去不含回文子串的个数。
那么如何判断是否有回文子串?
因为一个回文串,必定中间的$2$位或$3$位回文,那么如果一个数的任意连续$3$位都不一样,则不是回文串。
定义状态为 $dp[pos][num1][num2]$ 表示当前位为 $pos$,$pos+1$ 位为 $num1$,$pos+2$ 位为 $num2$。
答案可能会很大,一些优化:
- 一般最终答案都是 $solve(r)-solve(l-1)$,那么可以改为 $solve(r)-solve(l)+check(l)$
即单独判断 $l$,不用去写处理 $l-1$。 - 数的总个数也很多,所以可以在读入的时候先对 $l$ 和 $r$ 进行取模。
const int maxn = 1000+5;
int a[maxn];
char l[maxn], r[maxn];
ll dp[maxn][10][10];
ll dfs(int pos, int num1, int num2, bool lead, bool limit) {
if(pos == 0) return 1;
if(!limit && !lead && num1 != -1 && num2 != -1 && dp[pos][num1][num2] != -1) return dp[pos][num1][num2];
int up;
if(!limit) up = 9;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++) {
if(lead == true) {
if(i == 0) ans = (ans + dfs(pos - 1, -1, -1, true, (limit == true && i == a[pos]))) % Mod;
else ans = (ans + dfs(pos - 1, i, -1, false, (limit == true && i == a[pos]))) % Mod;
}
else if(i != num1 && i != num2) ans = (ans + dfs(pos - 1, i, num1, false, (limit == true && i == a[pos]))) % Mod;
}
if(!limit && !lead && num1 != -1 && num2 != -1)
dp[pos][num1][num2] = ans;
return ans;
}
ll solve(char num[]) {
memset(dp, -1, sizeof(dp));
int len = strlen(num + 1);
for(int i = 1;i <= len;i++) a[len - i + 1] = num[i] - '0';
return dfs(len, -1, -1, true, true);
}
int main() {
cin >> (l + 1) >> (r + 1);
ll numl = 0, numr = 0, len;
for(int i = 1;i <= strlen(l + 1);i++)
numl = (numl * 10 + l[i] - '0') % Mod;
for(int i = 1;i <= strlen(r + 1);i++)
numr = (numr * 10 + r[i] - '0') % Mod;
bool ok = true;
for(int i = 2;i <= strlen(l + 1);i++)
if(l[i] == l[i-1] || l[i] == l[i-2])
ok = false;
len = (numr - numl + 1 + Mod) % Mod;
cout << (len - (solve(r) - solve(l) + ok) + Mod) % Mod << endl;
return 0;
}
P3303 [SDOI2013]淘金
黑题数位dp,但其实还是比较简单的
由于 $f(x)$ 是 $x$ 的各位数字相乘,则我们可以统计每个数的$0\sim9$的个数,并且也能记忆化。
状态 $dp[pos][num1][num2][num3][num4][num5][num6][num7][num8][num9]$ 表示当前位为 $pos$,$1\sim9$ 各用了 $num_1 \sim num_9$ 次的数的个数。
由于 $f(x)=0$ 不在坐标轴范围内,则在搜索时判断即可。
然后愉快的发现: $N \le 10^{12}$。明显爆炸。
有没有方法优化呢?
后来想到:
- 一个数位$9$等价于两个数位$3$
- 一个数位$8$等价于三个数位$2$
- 一个数位$6$等价于一个数位$2$和一个数位$3$
- 一个数位$4$等价于两个数位$2$
- 数位$1$不会对 $f(x)$ 做出贡献
那么我们就可以将 $num4$,$num6$,$num8$,$num9$ 转化为 $num2$ 与 $num3$。并将 $num1$ 删除。
状态转化为 $dp[pos][num2][num3][num5][num7]$
$13^{10} \rightarrow 13\times 39\times 26\times 13\times 13$
现在我们就有了最终所有的 $f(x)$,但答案是二维的,并且让你取前 $k$ 大的和。
二维可以直接用 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n num_{f_i}\times num_{f_j}$ 得到,那么如何统计答案?
可以二分答案一个 $mid$,看有多少个值 $\ge mid$,最终找到恰好有 $k$ 个的情况即可。
注意:本题居然爆long long了,使用了一下__int128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll min(ll a, ll b) {return a < b ? a : b;}
inline ll max(ll a, ll b) {return a > b ? a : b;}
inline ll abs(ll x) {return x > 0 ? x : -x;}
const int Mod = 1000000007;
const int maxn = 15;
const int maxlen = 40 * 27 * 14 * 14 + 5;
int a[maxn], top, len;
ll n, k, dp[maxn][3 * maxn][2 * maxn][maxn][maxn], maxnum;
__int128 num[maxlen], sum[maxlen];
ll dfs(int pos, int num2, int num3, int num5, int num7, bool lead, bool limit) {
if(pos == 0) return (num2 + num3 + num5 + num7 + lead == 0);
if(!limit && !lead && dp[pos][num2][num3][num5][num7] != -1) return dp[pos][num2][num3][num5][num7];
int up;
if(!limit) up = 9;
else up = a[pos];
ll ans = 0;
for(int i = 0;i <= up;i++) {
if(i == 0 && lead == true) ans += dfs(pos - 1, num2, num3, num5, num7, true, (limit == true && i == a[pos]));
if(i == 1) ans += dfs(pos - 1, num2, num3, num5, num7, false, (limit == true && i == a[pos]));
if(i == 2 && num2 >= 1) ans += dfs(pos - 1, num2 - 1, num3, num5, num7, false, (limit == true && i == a[pos]));
if(i == 3 && num3 >= 1) ans += dfs(pos - 1,num2, num3 - 1, num5, num7, false, (limit == true && i == a[pos]));
if(i == 4 && num2 >= 2) ans += dfs(pos - 1, num2 - 2, num3, num5, num7, false, (limit == true && i == a[pos]));
if(i == 5 && num5 >= 1) ans += dfs(pos - 1, num2, num3, num5 - 1, num7, false, (limit == true && i == a[pos]));
if(i == 6 && num2 >= 1 && num3 >= 1) ans += dfs(pos - 1, num2 - 1, num3 - 1, num5, num7, false, (limit == true && i == a[pos]));
if(i == 7 && num7 >= 1) ans += dfs(pos - 1, num2, num3, num5, num7 - 1, false, (limit == true && i == a[pos]));
if(i == 8 && num2 >= 3) ans += dfs(pos - 1, num2 - 3, num3, num5, num7, false, (limit == true && i == a[pos]));
if(i == 9 && num3 >= 2) ans += dfs(pos - 1, num2, num3 - 2, num5, num7, false, (limit == true && i == a[pos]));
}
if(!limit && !lead)
dp[pos][num2][num3][num5][num7] = ans;
return ans;
}
void solve(int num2,int num3,int num5,int num7) {
ll ans = dfs(top, num2, num3, num5, num7, true, true);
num[++len] = ans;
maxnum = max(maxnum, ans);
}
void split(ll x) {
while(x != 0) {
a[++top] = x % 10;
x /= 10;
}
}
void write(__int128 x) {
if(!x) return;
if(x < 0) putchar('-'), x = -x;
write(x / 10);
putchar(x % 10 + '0');
}
bool check(__int128 x) {
int tot = 0;
for(int i = len, tag = 1;i >= 1 && tag <= len;i--) {
while(tag <= len && num[i] * num[tag] < x) tag++;
tot += len - tag + 1;
}
return tot < k;
}
int main() {
scanf("%lld%lld", &n, &k);
split(n);
memset(dp, -1, sizeof(dp));
for(int num2 = 0;num2 <= 39;num2++)
for(int num3 = 0;num3 <= 26;num3++)
for(int num5 = 0;num5 <= 13;num5++)
for(int num7 = 0;num7 <= 13;num7++)
solve(num2, num3, num5, num7);
sort(num + 1, num + len + 1);
__int128 l = 0,r = __int128(maxnum) * maxnum, mid, val;
while(l < r) {
mid = (l + r) >> 1;
if(check(mid) == true) r = mid;
else l = mid + 1;
}
val = l - 1;
for(int i = len;i >= 1;i--) sum[i] = (sum[i+1] + num[i]) % Mod;
ll ans = 0, cnt = 0;
for(int i = 1;i <= len;i++) {
int id = lower_bound(num + 1, num + len + 1, ceil(1.0 * val / num[i])) - num;
ans = (ans + num[i] % Mod * sum[id]) % Mod;
cnt += (len - id + 1);
}
if(cnt > k) ans = ((ans - val % Mod * (cnt - k) % Mod) + Mod) % Mod;
printf("%lld\n", ans);
return 0;
}
总结&吐槽
总的来说,数位dp可以直接套用记忆化模板,考虑好状态设计就行了,所以我认为还是一个简单的dp类型。
费了一下午的时间终于把坑给补上了,电脑都没电了qwq
还有两周就小中考和学校期末考试了,可能暑假之前就不能更新新的文章了,不过2021年目标还是会更新的。
顺便安排一下接下来学习笔记的内容:
- 树链剖分
- 可持久化系列
大概就是这样了,最后祝大家的小中考能有一个完美的成绩~