Warning: session_start(): open(/tmp/sess_52a999f5ea0f4aa1f6783b4b188aff99, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:动态规划_1 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:动态规划_1

动态规划 1

数位DP

算法简介

一般用于处理形如区间 $[l,r]$ 中满足条件的数有几个之类问题。

算法思想

首先考虑将区间 $[l,r]$ 拆分成 $[0,r]-[0,l]$。

考虑记忆化搜索,一般搜索函数为 $f(pos,s,eq,zero)$。

其中 $pos$ 表示当前搜索位置,$s$ 表示前缀状态,$eq$ 表示前缀是否与查询上界相等,$zero$ 表示是否有前导零。

算法练习

题意

询问区间 $[l,r]$ 中满足相邻数位之差至少为 $2$ 的数的个数。

题解

查看代码

查看代码

int a[10],dp[10][10];
int dfs(int pos,int pre,bool eq,bool zero){
	if(!pos)return 1;
	if(!eq&&~dp[pos][pre])return dp[pos][pre];
	int ans=0,v=eq?a[pos]:9;
	_rep(i,0,v){
		if(!zero&&abs(i-pre)<2)
		continue;
		ans+=dfs(pos-1,i,eq&&i==a[pos],zero&&i==0);
	}
	if(!eq&&!zero)dp[pos][pre]=ans;
	return ans;
}
int solve(int n){
	int len=0;
	mem(dp,-1);
	while(n){
		a[++len]=n%10;
		n/=10;
	}
	return dfs(len,0,true,true);
}
int main()
{
	int a=read_int(),b=read_int();
	printf("%d",solve(b)-solve(a-1));
	return 0;
}
2020-2021/teams/legal_string/jxm2001/动态规划_1.1596109786.txt.gz · 最后更改: 2020/07/30 19:49 由 jxm2001