社区讨论

关于数位 dp 的 dfs 和 for 写法

学术版参与者 3已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@mhj8wucu
此快照首次捕获于
2025/11/03 22:38
4 个月前
此快照最后确认于
2025/11/08 07:53
3 个月前
查看原帖
自认为 dfs 写法是从低位往高位填数,for 写法是从高位往低位填数,例如题目:萌数,以下是我的 dfs 写法代码:
CPP
ll dfs(ll pos, ll pre1, ll pre2, bool finish, bool not_zero, bool up) 
{
    if (pos > n) return finish;
    if (!up && ~f[pos][pre1][pre2][finish]) return f[pos][pre1][pre2][finish];
    ll end = up ? num[pos] : 9, ans = 0;
    for (int i = 0; i <= end; ++i) 
        ans = (ans + dfs(pos + 1, i, not_zero ? pre1 : -1, 
            finish || (i == pre1 || i == pre2) && not_zero, not_zero || i, up && end == i)) % mod;
    if (!up && not_zero && ~pre1 && ~pre2) f[pos][pre1][pre2][finish] = ans;
    return ans;
}
以下是我同学的 for 写法代码(可能较难看懂):
CPP
void _(int&x,int y){x+=x+y<P?y:y-P;}
int _(char*s){
	int n=strlen(s);
	if(n<2)return 0;
	for(i=n;i--;)for(j=10;j--;)for(k=10;k--;f[i][j][k]=g[i][j][k]=p[i][j][k]=q[i][j][k]=0);
	for(x=*s^48,y=s[1]^48,j=0;++j^x;)for(k=10;k--;)(j^k?p:f)[1][j][k]=1;
	for(k=y;k--;(x^k?p:f)[1][x][k]=1);
	for(i=1,(x^y?q:g)[1][x][y]=1;++i^n;){
		for(j=10;j--;)for(k=10;k--;)for(l=10;l--;)_(f[i][j][k],f[i-1][l][j]),_((l^k&&j^k?p:f)[i][j][k],p[i-1][l][j]);
		for(x=s[i-2]^48,y=s[i-1]^48,j=z=s[i]^48;j--;)_(f[i][y][j],g[i-1][x][y]),_((x^j&&y^j?p:f)[i][y][j],q[i-1][x][y]);
		for(j=10,_(g[i][y][z],g[i-1][x][y]),_((x^z&&y^z?q:g)[i][y][z],q[i-1][x][y]);--j;)for(k=10;k--;)_((j^k?p:f)[i][j][k],1);
	}
	for(S=0,j=10;j--;)for(k=10;k--;_(S,g[n-1][j][k]))_(S,f[n-1][j][k]);return S;
}
那这是不是意味着两个都要学?
万一特殊的题目让你只能从高往低位 dpdp,或者从低到高位 dpdp,只学一个就有 12\frac12 概率做不出来。

回复

11 条回复,欢迎继续交流。

正在加载回复...