Java教程

数位dp

本文主要是介绍数位dp,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

数位dp

目录
  • 数位dp
    • 简介
      • 同类分布
      • \(\text{Balanced Number}\)

简介

数位 \(dp\) 是一种在数位上进行的 \(dp\),通常用于解决值域 \([L,R]\) 中有几个数满足条件,且 \([L,R]\) 极大 (如 \(1\le L\le R\le 1e18\)) 的问题,这时我们就会在数位上进行 \(dp\),问题规模变为 \(\lg R\) 的

数位 \(dp\) 就是一次考虑数的每一位,且从高到低枚举 (因为高位限制低位的取值范围)

我们通常用 \(lim\) 变量来表示更高的数位是否都与 \(R\) 的对应位相同

如:\(R=123\),若前面两位取的 \(12\),那第 \(3\) 位只能为 \(0\sim 3\),若不是,则可以取 \(0\sim 9\)

我们通常使用记忆化搜索来实现数位 \(dp\)

数位 \(dp\) 模板:

inline ll dfs(int pos,int sum,int lim,...){
	if(!pos) {...}//数字填完了
	if(~f[pos][sum][rm][lim]) return f[pos][sum][rm][lim];//记忆化
	int mx=lim?a[pos]:9;//当前位最大是多少
	ll res=0;
	for(int i=0;i<=mx;++i)
		res+=dfs(pos+1,sum+i,lim&(i==mx),...);//填数
    f[pos][sum][rm][lim]=res;//记忆化
	return res;
}

https://vjudge.net/contest/513260

同类分布

以这道题为例说明一下数位 \(dp\) 的常规解法

记搜的时候我们记录 \(4\) 个变量:

\(pos\):当前搜到第几位

\(sum\):各位数字之和

\(rm\):原数对当前枚举的模数 \(mod\) 取模的结果

\(lim\):前几位是否和原数相同

这题我们的思路是枚举模数 \(mod\),然后通过记搜记录有几个符合要求,并统计答案

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

#define ll long long

int len,a[20],mod;
ll l,r,f[20][180][180][2];

inline ll dfs(int pos,int sum,int rm,int lim){
	if(pos>len&&!sum) return 0;
	if(pos>len) return (rm==0&&sum==mod);
	if(~f[pos][sum][rm][lim]) return f[pos][sum][rm][lim];
	int mx=lim?a[len-pos+1]:9;
	ll res=0;
	for(int i=0;i<=mx;++i)
		res+=dfs(pos+1,sum+i,1ll*(1ll*rm*10ll+i)%mod,lim&(i==mx));
    f[pos][sum][rm][lim]=res;
	return res;
}

inline ll solve(ll x){
	len=0;
	do{
		a[++len]=x%10;
		x/=10;
	}while(x);
	ll res=0;
	for(mod=1;mod<=9*len;++mod){
        memset(f,-1,sizeof(f));
		res+=dfs(1,0,0,1);
	}
	return res;
}

signed main(){
	cin>>l>>r;
	cout<<solve(r)-solve(l-1);
}

\(\text{Balanced Number}\)

这篇关于数位dp的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!