洛谷P4124 [CQOI2016]手机号码

凭感觉,要计算区间 [ L , R ] [L,R] [L,R]这些而且数目很大的,对数字位数有限制的,我们会考虑数位dp的模型 考虑状态 d p ( c u r , t o p , p r e 1 , p r e 2 , s t 1 , s t 2 ) dp(cur,top,pre1,pre2,st1,st2) dp(cur,top,pre1,pre2,st1,st2) 分别表示考虑到第 c u r cur cur个位置,是否贴着上界 t o p top top,前一个是 p r e 2 , 前两个是 p r e 1 pre2,前两个是pre1 pre2,前两个是pre1,是否已经满足条件1出现了3次相邻相同数字 s t 1 st1 st1 和 s t 2 = 0 既不包含 8 和 4 , s t 2 = 1 只包含 8 , s t 2 = 3 只包含 4 和st2=0既不包含8和4,st2=1只包含8,st2=3只包含4 和st2=0既不包含8和4,st2=1只包含8,st2=3只包含4. 然而以上状态并不能正确地通过测试,因为状态设计的并不正确,因为有重叠的部分. 就是说 s t 2 = 0 st2=0 st2=0包含的状态是既不包含4与8的数字 而 s t 2 = 1 , 是不包含 4 但是包含 8 st2=1,是不包含4但是包含8 st2=1,是不包含4但是包含8，也就是说这种情况我们必须要选一个8,不然就会进入 s t 2 = 0 的情况 st2=0的情况 st2=0的情况,同理 s t = 2 st=2 st=2也必须要选一个 4 4 4. 既然这样,我们转换一下 d p dp dp含义 d p ( c u r , t o p , p r e 1 , p r e 2 , s t 1 , a p 4 , a p 8 ) dp(cur,top,pre1,pre2,st1,ap4,ap8) dp(cur,top,pre1,pre2,st1,ap4,ap8): 选了第 c u r 个数字 , 是否贴着上界 t o p , 前 2 个数字是 p r e 1 , 前个数字是 p r e 2 , 是否出现过数字 a p 4 选了第cur个数字,是否贴着上界top,前2个数字是pre1,前个数字是pre2,是否出现过数字ap4 选了第cur个数字,是否贴着上界top,前2个数字是pre1,前个数字是pre2,是否出现过数字ap4 是否出现过数字 a p 8 是否出现过数字ap8 是否出现过数字ap8 注意不要第一位选0 狗啊,这题目还包含输入是10个,数字的情况,所以我们要特判掉

/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/
#include
using namespace std;
const int maxn = 15;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
ll dp[maxn][2][11][11][2][2][2];
int a[maxn];int len;
ll dfs(int cur,bool top,int pre1,int pre2,bool st1,bool ap4,bool ap8){
	if(!cur){
		if(ap4&&ap8) return 0;
		if(st1==0) return 0;
		return 1;
	}
	ll &ans = dp[cur][top][pre1][pre2][st1][ap4][ap8];
	if(ans!=-1) return ans;
	ans = 0;
	int bound = top ? a[cur] : 9;
	for(int i=0;i>L>>R;
	cout