Digital children < daily question> (Digital DP)

subject ：

---

  Topic link ： Sign in — major IT Written interview preparation platform _ Cattle from https://ac.nowcoder.com/acm/contest/23480/D

---

Ideas ：

digit dp The title of is usually a set of templates

Based on the original template

Change according to the subject conditions

So as to meet the requirements of the topic

The following three questions are analyzed

To meet the requirements of the topic 1 We have to be right

Sum every two adjacent digits

And judge whether it is a prime number

If not, proceed dfs

 

Because the title is required to be at least one digit 1

We don't know who is 1

So the judgment of this condition

You need to fill in this number completely before you can judge

If the digits have 1 And

No, 1 The situation of

 

General digits dp The topic will have some requirements  

We can go through lead

Find the highest position

In this way, you can remove the leading 0 Influence

---

Code details ：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<string.h>
const int N = 15;
#define int long long// take int The defined variable is converted to long long
bool check(int n)// Check whether it is prime 
{
	return n == 2 || n == 3 || n == 5 || n == 7 || n == 11
		|| n == 13 || n == 17 || n == 19;
}

int l, r, a[N], len, dp[N][N][2];// first [] What's the number , the second [] Indicates the number on this bit , Third [] Indicates whether it contains at least one 1
int dfs(int pos, int pre, int lead, int sum1, int limit)
{
	if (pos == 0) return sum1;// Traverse all digits , Number of schemes returned （ contains 1 Then return to 1, Otherwise return to 0）
	if (limit == 0 && lead==0  &&  dp[pos][pre][sum1] != -1) 
		return dp[pos][pre][sum1];// Not the highest position , There is no forerunner 0, And have been memorized （ Once traversed ）
	int up = limit ? a[pos] : 9;// Determine whether it is the highest 
	int ans = 0;
	for (int i = 0; i <= up; i++)
	{
		if (lead == 0 && check(pre + i)==0) continue;// There is no forerunner 0, And the addition of adjacent positions is not a prime number 
		ans += dfs(pos - 1, i, lead && i == 0, (i == 1) || sum1, limit && i == up);
	}
	// The front is not the highest position , There is no forerunner 0
	if ( limit == 0 && lead==0 ) 
		dp[pos][pre][sum1] = ans;// Memorization results 
	return ans;
}
int quwei(int n)
{
	len = 0;
	while (n) a[++len] = n % 10,n/=10;
	return dfs(len, 0,1,0,1);
}
signed main()// Pay attention to the int Transformed into long long  So use signed main)()
{
	cin >> l >> r;
	memset(dp, -1, sizeof(dp));
	cout << quwei(r) - quwei(l - 1)<<endl;
	return 0;
}

---

PS: I don't understand digital dp You can see what bloggers upload PPT Oh .