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

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;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115727.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • CentOS7关于网络的设置

    CentOS7关于网络的设置装好CentOS7后,我们一开始是上不了网的这时候,可以输入命令dhclient,可以自动获取一个IP地址,再用命令ipaddr查看IP不过这时候获取的IP是动态的,下次重启系统后,IP地址也会变化,这时候我们可以把系统的IP设置为静态的,设置步骤如下:(1)点击VMware虚拟机左上角的“编辑”,选择“虚拟网络编译器”。(2)选中VMnet8(NAT模式),再点击右侧的…

  • C++11新特性,利用std::chrono精简传统获取系统时间的方法

    C++11新特性,利用std::chrono精简传统获取系统时间的方法

  • 如何用纯 CSS 创作条形图,不用任何图表库

    如何用纯 CSS 创作条形图,不用任何图表库

  • Shell脚本调用阿里云API实现DDNS动态域名解析[通俗易懂]

    Shell脚本调用阿里云API实现DDNS动态域名解析[通俗易懂]由于服务器的外网是动态拨号,每次获取的外网IP都不同。手头上刚好有阿里云的域名。为此,想通过编写一个Shell脚本,定期通过互联网服务获取当前机器所在网络的IP地址,并将新的IP地址通过阿里云提供的API,更新到对应的域名解析记录。申请AccessKey登陆阿里云官网,在控制台的右上角,将鼠标移动到头像上,会出现如下列表:选择AccessKey管理,会弹出如下提示:选择开始使用子用户Access

  • 大数据平台建设经验「建议收藏」

    大数据平台建设经验「建议收藏」大数据平台建设技术背景Facebook的DREP原则!!思路建设流程经验教训生产案例饿了么大数据平台建设大数据平台逻辑架构图工具链架构图!!流入三个源数据流的UV计算渠道订单一个大数据平台省了20个IT人力——敦奴数据平台建设案例分享引跑科技副总裁张晓东:引跑DBone数据库助力大数据建设需求挖掘五步曲,快速建设大数据项目整合公司3个网站后台管理子系统的经验总结-实现多系统的单点登录(ASP.N

  • JAVA常见数据结构

    JAVA常见数据结构常见的的数据结构数据存储的常⽤结构有:栈、队列、数组、链表和红⿊树。栈栈:stack,⼜称堆栈,它是运算受限的线性表,其限制是仅允许在标的⼀端进⾏插⼊和删除操作,不允许在其他任何位置进⾏添加、查找、删除等操作。简单的说:采⽤该结构的集合,对元素的存取有如下的特点1.先进后出(即,存进去的元素,要在后它后⾯的元素依次取出后,才能取出该元素)。例如,⼦弹压进弹夹,先压进去的⼦弹在下⾯,后压进去的⼦弹在上⾯,当开枪时,先弹出上⾯的⼦弹,然后才能弹出下⾯的⼦弹。2.栈的⼊⼝、出⼝的都是栈的顶端位置。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号