启蒙

前段时间翔哥给大一们讲数位dp，很遗憾没能去听课，其实我没有做过也不会数位dp的题目，只好自学喽。刷了两道题有了一些学习心得，赶紧记下来，我真怕等会就忘了。

准备

1
2
3
4
5
6
7
8
int work(int x){
	int pos=0;
	while(x){
		dig[++pos] = x%10;
		x /= 10;
	}
	return dfs(pos,0,0,0,1);
}

很明显数位dp把一个数的每一位拆开了，用dp的是想去求解

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int dfs(int pos,int pre,int mod,bool have,bool limit){
	if( !pos ) return (have && !mod);
	if( !limit && dp[pos][pre][mod][have]!=-1)return dp[pos][pre][mod][have];
	int ans=0,end=limit?dig[pos]:9;
	for(int i=0 ; i<=end ; i++){
		if( pre == 1 && i ==3)
			ans += dfs(pos-1 , 3 , (mod*10+i)%13 , 1 , limit && ( i == dig[pos]) );
		else 
			ans += dfs(pos-1 , i ,(mod*10+i)%13 , have, limit && (i == dig[pos]) );
	}
	if(!limit)
		dp[pos][pre][mod][have] = ans;
	return ans;
}

在上面这个模板中

变量 意义
pos 当前处理的是第几位数字，例如13564，pos = 2从右往左数，处理的是 十位 ‘6’这个数字
pre 前一位数字的值，例如 13564 ,pos = 4,那么 pre =1,可以理解为大于pos位数的那个数字
mod 一般题目有什么要求，取余啊什么的，可以理解为state，状态
have 之前的状态下是否已经满足了题目要求
limit 精髓所在，表示有无约束，比如 13564，在处理 pos = 3 时（数字 ‘5’），万位是2时， 那么就没有限制，limit=0，因为pos = 3 那位可以取 0 - 9 ，都不会超过 13564。如果万位是3时，那么就有了约束，limit=1，因为pos = 3，那位只能去0 - 5 .

HDU_3652

赠送一道初学者的水题。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[15][10][13][2],dig[15],n;
int p[15];
int dfs(int pos,int pre,int mod,bool have,bool limit){
	if( !pos ) return (have && !mod);
	if( !limit && dp[pos][pre][mod][have]!=-1)return dp[pos][pre][mod][have];
	int ans=0,end=limit?dig[pos]:9;
	for(int i=0 ; i<=end ; i++){
		if( pre == 1 && i ==3)
			ans += dfs(pos-1 , 3 , (mod*10+i)%13 , 1 , limit && ( i == dig[pos]) );
		else 
			ans += dfs(pos-1 , i ,(mod*10+i)%13 , have, limit && (i == dig[pos]) );
	}
	if(!limit)
		dp[pos][pre][mod][have] = ans;
	return ans;
}
int work(int x){
	int pos=0;
	while(x){
		dig[++pos] = x%10;
		x /= 10;
	}
	return dfs(pos,0,0,0,1);
}
int main(){
	memset(dp,-1,sizeof(dp));
	while(cin>>n){
		cout<<work(n)<<endl;
	}
	return 0;
}