Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)

简介:

Imagine that you are in a building that has exactly n floors. You can move between the floors in a lift. Let's number the floors from bottom to top with integers from 1 to n. Now you're on the floor number a. You are very bored, so you want to take the lift. Floor number b has a secret lab, the entry is forbidden. However, you already are in the mood and decide to make k consecutive trips in the lift.

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 nabk (2 ≤ n ≤ 50001 ≤ k ≤ 50001 ≤ a, b ≤ na ≠ 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
2
input
5 2 4 2
output
2
input
5 3 4 1
output
0

题意:做电梯,刚開始的时候你在a层,不能到b层。每次你到新的地方的y,必须满足|x-y|<|x-b|,求坐k次有多少种可能

思路:比較easy想到的是dp[i][j]表示第i次到了j层的可能,分情况讨论。比如:当a<b的时候,下一次的层数i是不能超过j+(b-j-1)/2的。然后每次预先处理出前j层的可能。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
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) {
		dp[0][a] = 1;
		for (int j = 1; j < b; j++)
			sum[j] = sum[j-1] + dp[0][j];
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j < b; j++)
				dp[i][j] = (sum[(b-j-1)/2+j] - dp[i-1][j] + mod) % mod;
			sum[0] = 0;
			for (int j = 1; j < b; j++)
				sum[j] = (sum[j-1] + dp[i][j]) % mod;
		}
		printf("%d\n", sum[b-1]);
	}
	else {
		dp[0][a] = 1;
		for (int j = n; j >= b+1; j--)
			sum[j] = sum[j+1] + dp[0][j];
		for (int i = 1; i <= k; i++) {
			for (int j = b+1; j <= n; j++) 
				dp[i][j] = (sum[j-(j-b-1)/2] - dp[i-1][j] + mod) % mod;
			sum[0] = 0;
			for (int j = n; j >= b+1; j--)
				sum[j] = (sum[j+1] + dp[i][j]) % mod;
		}
		printf("%d\n", sum[b+1]);
	}
	return 0;
}







本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5261360.html,如需转载请自行联系原作者

相关文章
|
C++ 开发者
在C++语言中复合语句(块语句)
在C++语言中复合语句(块语句)
412 0
|
SQL JSON Apache
Flink问题之嵌套 json 中string 数组的解析异常如何解决
Apache Flink是由Apache软件基金会开发的开源流处理框架,其核心是用Java和Scala编写的分布式流数据流引擎。本合集提供有关Apache Flink相关技术、使用技巧和最佳实践的资源。
459 1
|
存储 缓存 编译器
从CPU缓存结构到原子操作-2
从CPU缓存结构到原子操作
211 0
|
Linux
linux开发各种I/O操作简析,以及select、poll、epoll机制的对比
linux开发各种I/O操作简析,以及select、poll、epoll机制的对比
407 1
linux开发各种I/O操作简析,以及select、poll、epoll机制的对比
|
Web App开发 监控 应用服务中间件
|
JSON JavaScript Java
highcharts插件使用总结和开发中遇到的问题及解决办法
这里使用的highchart是2014-01-09从官网下载的版本,版本号是3.0.8, 当过了几天后,发现版本号变成了3.0.9,不由得的感叹highchart的版本更新之快。 在jsp中使用highchart的步骤: 第一步:引入highchart必需的js文件 --...
1740 0