首页 > 代码库 > Ural 1586 Threeprime Numbers(DP)
Ural 1586 Threeprime Numbers(DP)
题目地址: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 <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> 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; }
Ural 1586 Threeprime Numbers(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。