G6005 [GESP202403 六级] 游戏 题解

知识点：递推、动态规划、取模。

解题思路

令dp[i]为当前数为i时的操作序列数。i≤c时仅有“立即结束”一种序列；否则分别选择减a或减b，方案数相加并取模。

为什么正确

按第一种操作分成两类不相交的序列，其后缀数量由较小状态给出，因此递推完整且无重复。

易错点

a==b时两种操作仍算不同，不能去重；减到负数时可并入已经结束的边界状态。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    const int M=1000000007;
    vector<int>dp(n+1,1);
    for(int i=c+1;i<=n;i++)dp[i]=(dp[max(0,i-a)]+(long long)dp[max(0,i-b)])%M;
    cout<<dp[n];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。