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

TOP

Ural 1586 Threeprime Numbers（DP）

2015-07-20 17:32:55 来源: 作者: 【大中小】浏览:2次

Tags：Ural 1586 Threeprime Numbers

题目地址：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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Binary Tree Level Order Travers..	下一篇：Path Sum

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: