URAL 1586 Threeprime Numbers（DP）

题意：定义Threeprime为它的任意连续3位上的数字，都构成一个3位的质数。求对于一个n位数，存在多少个Threeprime数。

思路：记录[100, 999]范围内所有素数（标记的是该素数的每一位x1,x2,x3）。然后从n = 4往后，定义dp[i][x2][x3], i 表示到第 i 位时，第 i-1 位为 x2 , 第 i 位x3，此时所包含的情况数。

dp[i][x2][x3] = dp[i][x2][x3] + dp[i-1][x1][x2]；最后求和sum(dp[n][x2][x3]);

 1 //1586
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #define MOD 1000000009
 6 #define LL long long
 7 using namespace std ;
 8 
 9 int dp[10010][10][10],prime[10][10][10] ;
10 int vis[1010] = {0} ,cnt = 0;
11 
12 void solve()
13 {
14     cnt = 0;
15     memset(vis,0,sizeof(vis)) ;
16     for(int i = 2 ; i <= 999 ; i++)
17     {
18         if(!vis[i])
19         {
20             for(int j = i*i ; j <= 999 ; j += i)
21                 vis[j] = 1 ;
22         }
23     }
24     for(int i = 100 ; i <= 999 ; i ++)
25     {
26         if(!vis[i])
27         {
28             int x1 = i / 100 ;
29             int x2 = i / 10 % 10 ;
30             int x3 = i % 10 ;
31             prime[x1][x2][x3] = 1;
32             dp[3][x2][x3] += 1 ;
33             cnt ++ ;
34         }
35     }
36 }
37 int main()
38 {
39     int n ;
40     scanf("%d",&n);
41     solve() ;
42     if(n == 3) {
43         printf("%d
",cnt % MOD) ;
44         return 0 ;
45     }
46     for(int i = 4 ; i <= n ; i++)
47         for(int x1 = 1 ; x1 <= 9 ; x1 ++)
48             for(int x2 = 1 ; x2 <= 9 ; x2 ++)
49                 for(int x3 = 1 ; x3 <= 9 ; x3 ++)
50                     if(dp[i-1][x1][x2]  && prime[x1][x2][x3])
51                         dp[i][x2][x3] = (dp[i][x2][x3] + dp[i-1][x1][x2]) % MOD;
52     int ans = 0 ;
53     for(int x2 = 1 ; x2 <= 9 ; x2 ++)
54     {
55         for(int x3 = 1 ; x3 <= 9 ; x3 ++)
56         {
57             ans = (ans+dp[n][x2][x3])%MOD ;
58         }
59     }
60     printf("%d
",ans) ;
61     return 0 ;
62 }

View Code