Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)_html/css_WEB-ITnose
Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y (y?≠?x) and the lift travels to this floor. As you cannot visit floor b with the secret lab, you decided that the distance from the current floor x to the chosen y must be strictly less than the distance from the current floor x to floor b with the secret lab. Formally, it means that the following inequation must fulfill: |x?-?y|?|x?-?b|. After the lift successfully transports you to floor y, you write down number y in your notepad.
Your task is to find the number of distinct number sequences that you could have written in the notebook as the result of k trips in the lift. As the sought number of trips can be rather large, find the remainder after dividing the number by 1000000007 (109?+?7).
Input
The first line of the input contains four space-separated integers n, a, b, k (2?≤?n?≤?5000, 1?≤?k?≤?5000, 1?≤?a,?b?≤?n, a?≠?b).
Output
Print a single integer ? the remainder after dividing the sought number of sequences by 1000000007 (109?+?7).
Sample test(s)
input
5 2 4 1
output
input
5 2 4 2
output
input
5 3 4 1
output
题意:做电梯,刚开始的时候你在a层,不能到b层,每次你到新的地方的y,必须满足|x-y|
思路:比较容易想到的是dp[i][j]表示第i次到了j层的可能,分情况讨论,例如:当a
#include#include #include #include #include using namespace std;const int mod = 1000000007;const int maxn = 5005;int n, a, b, k, dp[maxn][maxn];int sum[maxn];int main() { scanf("%d%d%d%d", &n, &a, &b, &k); memset(dp, 0, sizeof(dp)); if (a = b+1; j--) sum[j] = sum[j+1] + dp[0][j]; for (int i = 1; i = b+1; j--) sum[j] = (sum[j+1] + dp[i][j]) % mod; } printf("%d\n", sum[b+1]); } return 0;}
推荐阅读
-
Codeforces Round #274 (Div. 2) D. Long Jumps_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)D(树形DP计数类)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) C. Exams_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) C. Exams_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) A Expression_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) B. Towers_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) B Towers_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)D(树形DP计数类)_html/css_WEB-ITnose