P4893 游戏（提高）

解题思路

第一步，读懂题目。 你有四个正整数 n、a、b、c。每轮操作可以从 n 里减去 a，或者减去 b，一直减到 n≤c 为止。问一共有多少种不同的操作序列，答案对 1e9+7 取模。注意：就算 a=b，减去 a 和减去 b 也算两种不同的操作。

第二步，用动态规划数方案。 设 dp[i] 表示"当前数是 i 时，还能产生多少种不同的结束序列"。如果 i≤c，游戏已经结束，什么都不用做，只有 1 种序列，所以 dp[i]=1。如果 i>c，那么这一轮要么减 a 要么减 b，所以 dp[i]=dp[i-a]+dp[i-b]。

第三步，注意操作必须合法。 题目里减完的数不能是负数，也就是说只有当 i≥a 时才能执行"减 a"，只有当 i≥b 时才能执行"减 b"。如果一个数 i>c 但 i<a 且 i<b，它既不能减 a 也不能减 b，走不下去了，这种状态 dp[i]=0，不算合法的结束序列。

具体例子： 样例 n=1,a=1,b=1,c=1，一开始 n≤c，游戏直接结束，答案就是 1。再看 n=5,a=1,b=1,c=1：每一步可以从两个方向各来一次，相当于每一步都有 2 种选择，dp[2]=2×dp[1]=2，dp[3]=4，dp[4]=8，dp[5]=16。

边界情况： n 最大是 200000，所以 dp 数组要开到 200005。两个 dp 值相加可能很大，记得每一步都对 1e9+7 取模；为了安全先转成 long long 再加。

参考代码

// 游戏：n每轮减a或减b,直到n<=c,求不同操作序列数对1e9+7取模
#include <iostream>
using namespace std;

const int MOD = 1000000007;
int n, a, b, c;
int dp[200005]; // dp[i]表示当前数i能产生的序列数

int main() {
    cin >> n >> a >> b >> c;
    for (int i = 0; i <= c && i <= n; i++)
        dp[i] = 1; // 已经<=c,只有"不再操作"这一种序列
    for (int i = c + 1; i <= n; i++) {
        long long s = 0;
        // 只有i>=a才允许减a(结果不能为负), 减完<=c则序列记1
        if (i >= a) s += (i - a <= c) ? 1 : dp[i - a];
        // 减b同理; a与b相等也算不同操作, 所以两种都要加
        if (i >= b) s += (i - b <= c) ? 1 : dp[i - b];
        dp[i] = (int)(s % MOD);
    }
    cout << dp[n] << endl;
    return 0;
}

复杂度分析

只需要从 c+1 一直算到 n，每个数 O(1) 算一次，所以时间复杂度是 O(n)，n 最大 200000，很快。空间上用一个长度约 n 的数组，是 O(n)。