Ural 1586 Threeprime Numbers（DP） - c++编程基础

题目地址：Ural 1586

先定义一个prime三维数组来记录素数，若i*100+j*10+k为素数，则标记prime[i][j][k]为1，否则为0.这样对后面的处理很方便。

然后定义一个dp三维数组，dp[n][i][j]表示当前n位的十位数字为i,个位数字为j时的素数个数，这时候状态要从prime[k][i][j]为素数时转移过来，所以状态转移方程为：

if(prime[j][k][h]) dp[i][k][h]+=dp[i-1][j][k]

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; const int mod=1e9+9; int prime[11][11][11], dp[10001][10][10]; int main() { int i, j, k, n, h, x, flag, sum; memset(prime,0,sizeof(prime)); memset(dp,0,sizeof(dp)); for(i=1; i<=9; i++) { for(j=0; j<=9; j++) { for(k=1; k<=9; k++) { x=i*100+j*10+k; flag=0; for(h=2; h<=sqrt(x); h++) { if(x%h==0) { flag=1; break; } } if(!flag) prime[i][j][k]=1; dp[3][j][k]+=prime[i][j][k]; } } } scanf("%d",&n); for(i=4;i<=n;i++) { for(j=0;j<=9;j++) { for(k=0;k<=9;k++) { for(h=0;h<=9;h++) { if(prime[j][k][h]) { dp[i][k][h]+=dp[i-1][j][k]; dp[i][k][h]%=mod; } } } } } sum=0; for(i=0;i<=9;i++) { for(j=0;j<=9;j++) { sum+=dp[n][i][j]; sum%=mod; } } printf("%d\n",sum); return 0; }