题解

求赞qwq

传送门

一道略难的线性DP。

思路

dp[i]= 初始为i的不同操作序列数

• 对于$≤c$的i：初始即满足要求，“不操作”的操作序列数为1.
• 对于$>c$的i：为“-a”或“-b”的操作序列数总和（在i考虑，可由i-a和i-b到达）

代码

#include<bits/stdc++.h>
using namespace std;
const long long MOD=1000000007;
const long long N=2e5+10;

long long n,a,b,c,dp[N]; 

int main(){
	cin>>n>>a>>b>>c;
	
	for(long long i=0;i<=c;i++) dp[i]=1; //初始化，这部分的值为“不操作”的1
	
	for(long long i=c+1;i<=n;i++){ //从c+1开始，为">c"
		dp[i]=(dp[max(0LL,i-a)]+dp[max(0LL,i-b)])%MOD; //防止下标为负数，合理性：当i-a小于0时等价于<c的dp[0]
	}
	
	cout<<dp[n];
	
	return 0;
}