题解：P10376 [GESP202403 六级] 游戏

xyx404 · 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;
}