#include
#include
#include
using namespace std;
int visited[5][20][9009];// 访问情况
int dp[5][20][9009]; // M N num num即M-1位的数字
int num_2[7]= {2,3,5,7,11,13,17};
int num_3[9]= {2,3,5,7,11,13,17,19,23};
int num_4[11]= {2,3,5,7,11,13,17,19,23,29,31}; //存储素数
int N,M;
int delete_head(int num,int m) //去掉当前数字的首个数字
{
int ans;
if (m==2) return 0;
if (m==3) ans=num-num/10*10;
if (m==4) ans=num-num/100*100;
return ans;
}
int divide_num(int num)
{
int ans=0;
while (num>0)
{
ans+=num;
num=num/10;
}
return ans;
}
int select_num(int k,int sum,int m)
{
if (m==2)
{
for (int i=0; i<7; i++) if (k+divide_num(sum)==num_2[i]) return 1;
return 0;
}
if (m==3)
{
for (int i=0; i<9; i++)
if (k+divide_num(sum)==num_3[i])
{
return 1;
}
return 0;
}
if (m==4)
{
for (int i=0; i<11; i++) if (k+divide_num(sum)==num_4[i]) return 1;
return 0;
}
}
void work(int m,int n,int num)
{
if (n==0) // n=0直接处理
{
visited[m][n][num]=1;
dp[m][n][num]=1;
}
else
{
if (!visited[m][n][num])
{
visited[m][n][num]=1;
for (int k=0; k<=9; k++)
{
if (select_num(k,num,m))
{
int next=delete_head(num,m)*10+k; //next是num的下个状态（去头加尾）
if (!visited[m][n-1][next])
{
work(m,n-1,next);
}
dp[m][n][num]+=dp[m][n-1][next];
}
}
}
}
}
int main()
{
memset(visited,0,sizeof(visited));
memset(dp,0,sizeof(dp));
scanf("%d %d",&N,&M);
if (M==1)
{
int ans=1;
while (N>0)
{
ans*=4;
N--;
}
printf("%d\n",ans);
}
if (M==2)
{
int ans=0;
for (int i=0; i<=9; i++)
{
int num=i;
work(M,N-1,num);
ans+=dp[M][N-1][num];
}
printf("%d\n",ans);
}
if (M==3)
{
int ans=0;
for (int i=0; i<=9; i++)
for (int k=0; k<=9; k++)
{
int num=i*10+k;
work(M,N-2,num);
ans+=dp[M][N-2][num];
}
printf("%d\n",ans);
}
if (M==4)
{
int ans=0;
for (int i=0; i<=9; i++)
for (int k=0; k<=9; k++)
for (int x=0; x<=9; x++)
{
int num=i*100+k*10+x;
work(M,N-3,num);
ans+=dp[M][N-3][num];
}
printf("%d\n",ans);
}
return 0;
}
小明的密码由N（1<=N<=12）个数字构成，每个数字都可以是0至9中任意一个数字，但小明的密码还有 一个特点就是密码中连续的M（1<=M<=4）个数字的和是质数，现给定M和N，求满足条件的密码共有多少 个？ 输入格式 第1行是T，case数量，此后T行，每行两个数，N和M 输出格式 每个case输出一个满足条件的密码总数
输入样例
2
1 1
2 1
输出样例
4
16
作者 admin
第一次做多维DP，虽然才做到第三个维度，感觉已经够狠的题目还可以出的更复杂，比如M更大的时候我还没想过怎么操作，暂时做到三维DP，主要是做第三维的时候遇到困难，第一次做的时候把前M-1位的数字和求出来做参数，没想到维度混淆了，还是只能用M-1做真整数，这样如果M稍微大一点，我可能都要做高精度了，而且内存也不宽裕，继续努力想其他解法吧
1 #include
2 #include
3 #include
4 using namespace std;
5 int visited[5][20][9009];// 访问情况
6 int dp[5][20][9009]; // M N num num即M-1位的数字
7 int num_2[7]= {2,3,5,7,11,13,17};
8 int num_3[9]= {2,3,5,7,11,13,17,19,23};
9 int num_4[11]= {2,3,5,7,11,13,17,19,23,29,31}; //存储素数
10 int N,M;
11 int delete_head(int num,int m) //去掉当前数字的首个数字
12 {
13 int ans;
14 if (m==2) return 0;
15 if (m==3) ans=num-num/10*10;
16 if (m==4) ans=num-num/100*100;
17 return ans;
18 }
19 int divide_num(int num)
20 {
21 int ans=0;
22 while (num>0)
23 {
24 ans+=num;
25 num=num/10;
26 }
27 return ans;
28 }
29 int select_num(int k,int sum,int m)
30 {
31 if (m==2)
32 {
33 for (int i=0; i<7; i++) if (k+divide_num(sum)==num_2[i]) return 1;
34 return 0;
35 }
36 if (m==3)
37 {
38 for (int i=0; i<9; i++)
39 if (k+divide_num(sum)==num_3[i])
40 {
41 return 1;
42 }
43 return 0;
44 }
45 if (m==4)
46 {
47 for (int i=0; i<11; i++) if (k+divide_num(sum)==num_4[i]) return 1;
48 return 0;
49 }
50 }
51 void work(int m,int n,int num)
52 {
53 if (n==0) // n=0直接处理
54 {
55 visited[m][n][num]=1;
56 dp[m][n][num]=1;
57 }
58 else
59 {
60 if (!visited[m][n][num])
61 {
62 visited[m][n][num]=1;
63 for (int k=0; k<=9; k++)
64 {
65 if (select_num(k,num,m))
66 {
67 int next=delete_head(num,m)*10+k; //next是num的下个状态（去头加尾）
68 if (!visited[m][n-1][next])
69 {
70 work(m,n-1,next);
71 }
72 dp[m][n][num]+=dp[m][n-1][next];
73 }
74 }
75 }
76 }
77 }
78 int main()
79 {
80 memset(visited,0,sizeof(visited));
81 memset(dp,0,sizeof(dp));
82 scanf("%d %d",&N,&M);
83 if (M==1)
84 {
85 int ans=1;
86 while (N>0)
87 {
88 ans*=4;
89 N--;
90 }
91 printf("%d\n",ans);
92 }
93 if (M==2)
94 {
95 int ans=0;
96 for (int i=0; i<=9; i++)
97 {
98 int num=i;
99 work(M,N-1,num);
100 ans+=dp[M][N-1][num];
101 }
102 printf("%d\n",ans);
103 }
104 if (M==3)
105 {
106 int ans=0;
107 for (int i=0; i<=9; i++)
108 for (int k=0; k<=9; k++)
109 {
110 int num=i*10+k;
111 work(M,N-2,num);
112 ans+=dp[M][N-2][num];
113 }
114 printf("%d\n",ans);
115 }
116 if (M==4)
117 {
118 int ans=0;
119 for (int i=0; i<=9; i++)
120 for (int k=0; k<=9; k++)
121 for (int x=0; x<=9; x++)
122 {
123 int num=i*100+k*10+x;
124 work(M,N-3,num);
125 ans+=dp[M][N-3][num];
126 }
127 printf("%d\n",ans);
128 }
129 return 0;
130 }