程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Ural 1586 Threeprime Numbers（DP）

Ural 1586 Threeprime Numbers（DP）

編輯：C++入門知識

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 
#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;
}