题解：P10376 [GESP202403 六级] 游戏
题目传送门
本蒟蒻第一次写题解。
尤其是扶苏老师的
回归题目
这道题我们肯定首先考虑模拟。
模拟，又或者说是暴力，肯定用了比
又是 而且本人也没能想出模拟方案
我们在求每次决定后的最终方案数，是不是不同的？是不是是未知的？
如果当成递归的写法呢？每次决定的方案数在归的步骤就在计算，省了一些功夫来处理他们
而且时间复杂度将会有指数级（我也不知道是不是指数级的)下降，空间也是。
并且我们只需要考虑出口和递出去的条件就好了：
出口正是题目所说：
递出去也不正是
思路来喽！！！直接拿下
半成品如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; //将long long 简写成 ll
const int N=1e6+10; //个人习惯打1e6+10的空间
const ll mod=1e9+7;
ll n,a,b,c;
ll dfs(ll u)
{
if(u<=c) return 1;
return (dfs(u-a)%mod+dfs(u-b)%mod)%mod;
}
signed main() //本蒟蒻小小的装一下signed是有符号的思，可以代替int
{
cin>>n>>a>>b>>c;
cout<<dfs(n);
return 0;
}当然结果肯定不是这样的。
但是又说回来了，上面那样递归时间复杂度是多少呢？这不就是无记忆化吗？！
这就像一颗树一样，会有许多分叉，并且，这些分叉还有相同的，这些分叉肯定再计算就太麻烦了。
前面所说：“并且，这些分叉还有相同的”。
所以要写一个记忆化搜索
AC 代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; //将long long 简写成 ll
const int N=2e5+10;
const ll mod=1e9+7;
ll n,a,b,c;
map <ll,ll> f; //记忆化搜索以防重复答案耗费时间复杂度
//因为数组有限，所以用了map来映射答案
ll dfs(ll u)
{
if(f[u]!=0) return f[u];
if(u<=c) return 1;
return f[u]=(dfs(u-a)%mod+dfs(u-b)%mod)%mod;
}
signed main() //本蒟蒻小小的装一下，signed是有符号的意思，可以代替int
{
cin>>n>>a>>b>>c;
cout<<dfs(n)%mod;
return 0;
}无注释版：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll mod=1e9+7;
ll n,a,b,c;
map <ll,ll> f;
ll dfs(ll u)
{
if(f[u]!=0) return f[u];
if(u<=c) return 1;
return f[u]=(dfs(u-a)%mod+dfs(u-b)%mod)%mod;
}
signed main()
{
cin>>n>>a>>b>>c;
cout<<dfs(n)%mod;
return 0;
}AC记录