大家好,又见面了,我是全栈君。
E. Riding in a Lift
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 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
2
input
5 2 4 2
output
2
input
5 3 4 1
output
0
Note
Two sequences p1, p2, …, pk and q1, q2, …, qk are distinct, if there is such integer j (1 ≤ j ≤ k), that pj ≠ qj.
Notes to the samples:
上次的cf今天才补题o(╯□╰)o,给n层楼。在a层開始,不能在b层停,且当在x层去y层时。|x - y| < |x - b|,求运行k
次的方案数。
有两种情况,dp[i][j],i为第i次,j为当前停的层数。
当a<b时,此时全部的x不会超过b,当第i次停在j层。第i-1次肯定在[0,(b+j-1)/2],左端点不难想到,右端点推导过程:
设第i-1次停在x层。则第i层全部大于x小于b的点都能够取。我们仅仅考虑小于x的点。则x-j<=b-x-1,
整理得: x<=(b+j-1)/2; 所以转移方程为:dp[i][j]=(sum[i-1][(j+b-1)/2]-dp[i-1][j]+mod)%mod;
当a>b时,同理得 dp[i][j]=((sum[i-1][n]-sum[i-1][(j+b)/2]+mod)%mod-dp[i-1][j]+mod)%mod;
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=5000+100;
const int mod=1000000000+7;
int dp[maxn][maxn];
int sum[maxn][maxn];
int n;
void getsum(int x)
{
for(int i=1;i<=n;i++)
{
sum[x][i]=(sum[x][i-1]+dp[x][i])%mod;
// printf("%I64d\n",sum[x][i]);
}
}
int main()
{
int a,b,k;
scanf("%d%d%d%d",&n,&a,&b,&k);
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
dp[0][a]=1;
if(a<b)
{
getsum(0);
for(int i=1;i<=k;i++)
{
for(int j=1;j<b;j++)
{
dp[i][j]=(sum[i-1][(j+b-1)/2]-dp[i-1][j]+mod)%mod;
// printf("%I64d ",dp[i][j]);
}
// printf("\n");
getsum(i);
}
}
else
{
getsum(0);
for(int i=1;i<=k;i++)
{
for(int j=b+1;j<=n;j++)
{
//printf("%d %d\n",sum[i-1])
dp[i][j]=((sum[i-1][n]-sum[i-1][(j+b)/2]+mod)%mod-dp[i-1][j]+mod)%mod;
// printf("%d ",dp[i][j]);
}
getsum(i);
}
}
long long ans=0;
for(int i=1;i<=n;i++)
{
ans=(ans+dp[k][i])%mod;
//printf("%d ",dp[k][i]);
}
printf("%I64d\n",ans);
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116125.html原文链接:https://javaforall.cn