Problem 2156 Climb Stairs
Problem Description
Jason lives on the seventh floor. He can climb several stairs at a time, and he must reach one or more specific stairs before he arrives home because of obsessive-compulsive disorder.
Let us suppose:
1. Jason can climb X stairs or Y stairs at a time.
2. Jason wants to reach the N th stairs.
3. Jason must reach the Ath stairs and the Bth stairs before he reaches the Nth stairs.
Now, Jason wants to know how many ways he can reach the Nth stairs.
Input
The input will consist of a series of test cases.
Each test case contains five integer: N, X, Y, A, B.
0<N<=10,000
0<X, Y<=10,000
0<A, B<=N
Output
For each test case, output the answer mod 1,000,000,007.
Sample Input
3 1 2 2 1
5 2 3 1 1
Sample Output
1
0
代码：
/**
* dp, 当走到i+x层时，dp[i+x]=dp[i]+dp[i+x]
* 即上升x层后到达楼层的ways = 上升之前的ways + 上升后楼层以前的ways
*
*/
#include <stdio.h>
#include <string.h>
#define MAX 10005
int dp[MAX];
int n, x, y, a, b;
int fun(int l, int r)
{
for (int i = l; i <= r; i++){
if ((i + x) <= r)
dp[i + x] = (dp[i] + dp[i + x]) % 1000000007;
if ((i + y) <= r)
dp[i + y] = (dp[i] + dp[i + y]) % 1000000007;
}
return dp[r] % 1000000007;
}
int main()
{
while (scanf("%d%d%d%d%d", &n, &x, &y, &a, &b) != EOF)
{
if (a > b){ int m = a; a = b; b = m; }
memset(dp, 0, sizeof(dp));
dp[0] = 1;
int u1 = fun(0, a);
if (0 == u1){ puts("0"); continue; }
int u2 = fun(a, b);
if (0 == u2){ puts("0"); continue; }
int ans = fun(b, n) % 1000000007;
printf("%d\n", ans);
}
return 0;
}