题目链接:https://www.lanqiao.cn/problems/1027/learning/
一道dp题,但是用普通三维dp最多只能的30%的测试点,记忆化搜索同理。
快筛一遍质数,然后用三维dp再然后剪枝可以过40%测试点的样子。
给出大佬的代码:https://blog.csdn.net/CallmeChallenger/article/details/117533936?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-117533936-blog-117431246.pc_relevant_multi_platform_whitelistv2&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-117533936-blog-117431246.pc_relevant_multi_platform_whitelistv2&utm_relevant_index=1
值得多看看学学。这种三维转二维思路
然后就是我的30%
#include<bits/stdc++.h> using namespace std; int dp[500][500][500]; int r1,c1,h1,r2,c2,h2; const int mod = 1e9+7; bool is_zhishu(int x) { for(int i=2;i<=sqrt(x);i++) { if(x%i==0) { return false; } } return true; } bool is_xianjing(int i,int j,int k) { if(i==r1&&j==c1&&k==h1||i==r2&&j==c2&&k==h2) return true; return false; } int main() { //从 1,1,1走到 n,m,w 的走法 //每次只能走质数格 ,每次只能向东、南、上走 //我们可以考虑使用dp ,当前位置走到的次数是它的西、北、下走的次数 int n,m,w; cin>>n>>m>>w; cin>>r1>>c1>>h1>>r2>>c2>>h2; dp[1][1][1] = 1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=1;k<=w;k++) { if(!is_xianjing(i,j,k)) { //先从北开始吧 for(int ff=2;ff<i;ff++) { if(is_zhishu(ff)&&i-ff>=1&&!is_xianjing(i-ff,j,k)) dp[i][j][k]+=dp[i-ff][j][k]%mod,dp[i][j][k]%=mod; } //然后是西 for(int ff=2;ff<j;ff++) { if(is_zhishu(ff)&&j-ff>=1&&!is_xianjing(i,j-ff,k)) dp[i][j][k]+=dp[i][j-ff][k]%mod,dp[i][j][k]%=mod; } //最后是下 for(int ff=2;ff<k;ff++) { if(is_zhishu(ff)&&k-ff>=1&&!is_xianjing(i,j,k-ff)) dp[i][j][k]+=dp[i][j][k-ff]%mod,dp[i][j][k]%=mod; } } } } } cout<<dp[n][m][w]; }