自动搬运

查看原文

来自洛谷，原作者为

	xyx404 发接龙拉黑 | 新初三|蒟蒻| Link3 聚合页 link3.cc/xyx404 | 个人博客链接 xyx404.github.io

搬运于2025-08-24 22:57:22，当前版本为作者最后更新于2024-04-27 16:59:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

先写出暴力的搜索，然后改为记忆化搜索。

暴力的搜索就是暴力向下搜 $n$ 减去 $a$ 和 $n$ 减去 $b$ 的游戏操作序列的总数，暴力搜索代码如下。

long long dfs(long long x){
	if(x<=c)return 1;
	return (dfs(x-a)%mod+dfs(x-b)%mod)%mod;
}

然后改为记忆化搜索，定义一个数组存结果，如果现在搜索的这个数已经被搜索过了就自己访问数组，如果没有就先搜索，搜索完后赋值，这样就可以防止重复地搜索一个数，记忆化搜索代码如下。

long long dfs(long long x){
	if(x<=c)return 1;
	if(an[x]!=0)return an[x];// 如果有值直接返回
	return an[x]=(dfs(x-a)%mod+dfs(x-b)%mod)%mod;// 如果没有进行搜索并赋值
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
long long an[200005]={0};
long long n,c,b,a;
const int mod=1e9+7;// 模 1e9+7
long long dfs(long long x){
	if(x<=c)return 1;
	if(an[x]!=0)return an[x];// 如果有值直接返回
	return an[x]=(dfs(x-a)%mod+dfs(x-b)%mod)%mod;// 如果没有进行搜索并赋值
}
int main(){
	cin>>n>>a>>b>>c;
	cout<<dfs(n);
	return 0;
}