gesp(C++六级)（7）洛谷：P10376：[GESP202403 六级] 游戏

题目描述

你有四个正整数 $n,a,b,c$，并准备用它们玩一个简单的小游戏。

在一轮游戏操作中，你可以选择将 $n$ 减去 $a$，或是将 $n$ 减去 $b$。游戏将会进行多轮操作，直到当 $n\le c$ 时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将 $n$ 减去 $a$，而另一种操作序列选择将 $n$ 减去 $b$。如果 $a=b$，也认为将 $n$ 减去 $a$ 与将 $n$ 减去 $b$ 是不同的操作。

由于答案可能很大，你只需要求出答案对 $10^9+7$ 取模的结果。

输入格式

一行四个整数 $n,a,b,c$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1 1 1 1

样例输出 #1

1

样例 #2

样例输入 #2

114 51 4 1

样例输出 #2

176

样例 #3

样例输入 #3

114514 191 9 810

样例输出 #3

384178446

提示

数据规模与约定

• 对 $20\%$ 的数据，$a=b=c=1$，$n\le 30$。
• 对 $40\%$ 的数据，$c=1$，$n\le 10^3$。
• 对全部的测试数据，保证 $1\le a,b,c\le n\le 2\times 10^5$。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*思路2： 
	动态规划：
	dp[i]含义:当n=i的方案数
	状态转移方程：
		当i<=c时，dp[i]=1; 
	    当i>c时，dp[i]=dp[i-a]+dp[i-b]	
*/
ll n,a,b,c;//注意开long long 
ll dp[200010];//dp数组 
const int N=1e9+7; 
int main(){
	cin>>n>>a>>b>>c;
	//特判
	if(n<=c){
		cout<<1;
		return 0;
	} 
	//递推
	for(int i=0;i<=c;i++) dp[i]=1;
	for(int i=c+1;i<=n;i++){
//		dp[i]=(dp[i-a]%N+dp[i-b]%N)%N;//对比：注意这种写法没有考虑i-a和i-b可能为负数
		dp[i]=(dp[max(i-a,0ll)]%N+dp[max(i-b,0ll)]%N)%N;
	} 
	//输出答案
	cout<<dp[n]; 
	return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容