题目链接: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];
 }