蓝桥杯国赛---质数行者（3维dp）

叁歲伎倆 2021-07-16 16:53 597阅读 0赞

【问题描述】  
小蓝在玩一个叫质数行者的游戏。  
游戏在一个 n×m×w 的立体方格图上进行，从北到南依次标号为第 1 行到  
第 n 行，从西到东依次标号为第 1 列到第 m 列，从下到上依次标号为第 1 层到第 w 层。  
小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w层。每一步，他可以向东走质数格、向南走质数格或者向上走质数格。每走到一个位置，小蓝的角色要稍作停留。  
在游戏中有两个陷阱，分别为第 r 1 行第 c 1 列第 h 1 层和第 r 2 行第 c 2 列第h2 层。这两个陷阱的位置可以跨过，但不能停留。也就是说，小蓝不能控制角色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。  
小蓝最近比较清闲，因此他想用不同的走法来完成这个游戏。所谓两个走法不同，是指小蓝稍作停留的位置集合不同。  
请帮小蓝计算一下，他总共有多少种不同的走法。  
提示：请注意内存限制，如果你的程序运行时超过内存限制将不得分。  
【输入格式】  
输入第一行包含两个整数 n, m, w，表示方格图的大小。  
第二行包含 6 个整数，r 1 , c 1 , h 1 , r 2 , c 2 , h 2 ，表示陷阱的位置。  
【输出格式】  
输出一行，包含一个整数，表示走法的数量。答案可能非常大，请输出答  
案除以 1000000007 的余数。  
【样例输入】  
5 6 1  
3 4 1 1 2 1  
【样例输出】  
11  
【样例说明】  
用 (r,c,h) 表示第 r 行第 c 列第 h 层，可能的走法有以下几种：

1.(1,1,1) − (1,3,1) − (1,6,1) − (3,6,1) − (5,6,1)。  
2.(1,1,1) − (1,3,1) − (3,3,1) − (3,6,1) − (5,6,1)。  
3.(1,1,1) − (1,3,1) − (3,3,1) − (5,3,1) − (5,6,1)。  
4.(1,1,1) − (3,1,1) − (3,3,1) − (3,6,1) − (5,6,1)。  
5.(1,1,1) − (3,1,1) − (3,3,1) − (5,3,1) − (5,6,1)。  
6.(1,1,1) − (3,1,1) − (5,1,1) − (5,3,1) − (5,6,1)。  
7.(1,1,1) − (3,1,1) − (5,1,1) − (5,4,1) − (5,6,1)。  
8.(1,1,1) − (1,4,1) − (1,6,1) − (3,6,1) − (5,6,1)。  
9。(1,1,1) − (1,6,1) − (3,6,1) − (5,6,1)。  
10.(1,1,1) − (3,1,1) − (3,6,1) − (5,6,1)。  
11.(1,1,1) − (3,1,1) − (5,1,1) − (5,6,1)。  
【评测用例规模与约定】  
对于 30% 的评测用例 1 ≤ n,m,w ≤ 50。  
对于 60% 的评测用例 1 ≤ n,m,w ≤ 300。  
对于所有评测用例，1 ≤ n,m,w ≤ 1000，1 ≤ r 1 ,r 2 ≤ n, 1 ≤ c 1 ,c 2 ≤ m,  
1 ≤ h 1 ,h 2 ≤ w，陷阱不在起点或终点，两个陷阱不同。

## 思路 ##

这个算法只能过60%，刚好卡在空间和时间的极限。  
用p数组记录前300的质数。  
dp\[i\]\[j\]\[k\]代表走到第(i,j,k)位置时有多少种走法。  
状态转移方程：  
若(i,j,k)为陷阱点直接为0 dp\[i\]\[j\]\[k\]=0  
若不为陷阱  
dp\[i\]\[j\]\[k\]+=dp\[i-p\[u\]\]\[j\]\[k\] (i>=p\[u\]，枚举u=1，u=2，u=…)  
表示第i行j列k层可由i-p\[u\]行j列k层走到。  
同理可得，也能由在上列移动和在层移动得到  
dp\[i\]\[j\]\[k\]+=dp\[i\]\[j-p\[u\]\]\[k\] (i>=p\[u\]，枚举u=1，u=2，u=…)  
dp\[i\]\[j\]\[k\]+=dp\[i\]\[j\]\[k-p\[u\]\] (i>=p\[u\]，枚举u=1，u=2，u=…)

#include <iostream>
    using namespace std;
    typedef long long ll;
    
    int dp[305][305][305];
    int p[305];
    int Mod = 1e9 + 7;
    
    int main()
    { 
        int n, m, h;cin >> n >> m >> h;
        int x, y, z, x1, y1, z1;
        cin >> x >> y >> z >> x1 >> y1 >> z1;
        int u = 0;
        dp[1][1][1] = 1;
        for (int i = 2;i <= 305;i++)
        { 
            int f = 1;
            for (int j = 2;j * j <= i;j++)
            { 
                if (i % j == 0)f = 0;
            }
            if (f)   p[++u] = i;
        }
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++)
            { 
                for (int k = 1;k <= h;k++)
                { 
                    if (i == x && j == y && z == k)continue;
                    if (i == x1 && j == y1 && k == z1)continue;
                    for (int l = 1;l <= 70;l++)
                    { 
                        if (i - p[l] >= 0)dp[i][j][k] = (dp[i][j][k]+dp[i - p[l]][j][k])%Mod;
                        else break;//剪枝
                    }
                    for (int l = 1;l <= 70;l++)
                    { 
                        if (j - p[l] >= 0)dp[i][j][k] = (dp[i][j][k]+dp[i][j - p[l]][k])%Mod;
                        else break;
                    }
                    for (int l = 1;l <= 70;l++)
                    { 
                        if (k - p[l] >= 0)dp[i][j][k] = (dp[i][j][k]+dp[i][j][k - p[l]])%Mod;
                        else break;
                    }
                }
            }
        cout << dp[n][m][h];
    }