小红的难题<递推>

题意:五个数:N,x,y,A,B;N是台阶总数,x,y是每步可以走x或者y步,但是一定要走到A,B台阶上。

思路:学长给的题解,递推,稍微优化一点。

>重点在递推

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,A,B,x,y;
const ll mod=1000000007;
ll dp[10005];
int main (){
while(~scanf("%d%d%d%d%d",&n,&x,&y,&A,&B)){
if(A>B)
swap(A,B);
memset(dp,0,sizeof(dp));
dp[0]=1;
ll ed=max(A,max(B-A,n-B));
for(int i=1;i<=ed;i++){
if(i>=x)(dp[i]+=dp[i-x])%=mod;
if(i>=y)(dp[i]+=dp[i-y])%=mod;
}
ll ans=((dp[A]%mod)*(dp[B-A]%mod))%mod;
ans=((ans%mod)*(dp[n-B]%mod))%mod;
printf("%lld\n",ans);
}
return 0;
}

上一篇:linux内核分析 第六周 分析Linux内核创建一个新进程的过程


下一篇:echarts图表里遇到的问题