Time Limit:5000ms Memory Limit:64MB

题目描述

LYK 在一幢大楼里，这幢大楼共有 n 层，LYK 初始时在第 a 层上。
这幢大楼有一个秘密实验室，在第 b 层，这个实验室非常特别，对 LYK 具有约束作用，
即若 LYK 当前处于 x 层，当它下一步想到达 y 层时，必须满足|x-y|<|x-b|，而且由于实验室
是不对外开放的，电梯无法停留在第 b 层。
LYK 想做一次旅行，即它想按 k 次电梯，它想知道不同的旅行方案个数有多少个。
两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。

输入格式(lab.in)

一行 4 个数，n,a,b,k。

输出格式(lab.out)

一个数表示答案，由于答案较大，将答案对 1000000007 取模后输出。

输入样例 1

5 2 4 1

输出样例 1

2

输入样例 2

5 2 4 2

输出样例 2

2

输入样例 3

5 3 4 1

输出样例 3

数据范围

对于 20%的数据 n,k<=5。
对于 40%的数据 n,k<=10。
对于 60%的数据 n,k<=500。
对于 90%的数据 n,k<=2000。
对于 100%的数据 n,k<=5000。

题解：

DP+滚动数组

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long mod = 1000000007;
int n, a, b, k;
long long ans;
int xl[2333], cs[2333];
bool used[2333], lsu[2333];
long long dp[2][5002], sum[5002];
void dfs(int s, int cnt)
{
	if (cnt == k)
	{
		ans++;
		ans %= mod;
		return ;
	}
	int x = abs(s - b);
	for (int i = 1; i < x; i++)
	{
		if (s+i == b || s-i == b)
			continue;
		if (s+i <= n)
			dfs(s+i, cnt+1);
		if (s-i >= 1)
			dfs(max(s-i, 1), cnt+1);
	}
}
int main()
{
	cin >> n >> a >> b >> k;
	if (k <= 10)
	{
		ans = 0;
		dfs(a, 0);
		cout << ans%mod << endl;
	}
	else
	{
		if (a >= b)
			n -= b, a -= b;
		else
			n = b-1, a = b - a;
		dp[0][a] = 1;
		for (int i = 1; i <= k; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				sum[j] = sum[j-1] + dp[(i+1)%2][j];
				sum[j] %= mod;
			}
			for (int j = 1; j <= n; j++)
			{
				int ls = i % 2;
				dp[ls][j] = sum[n] - sum[j];
				int p = j/2;
				dp[ls][j] += sum[j-1] - sum[p];
				while (dp[ls][j] < 0)
					dp[ls][j] += mod;
				dp[ls][j] %= mod;
			}
		}
		ans = 0;
		k%=2;
		for (int i = 1; i <= n; i++)
		{
			ans += dp[k][i];
			while (ans < 0)
				ans += mod;
			ans %= mod;
		}
		cout << ans;
	}
	return 0;
}