LYK 与实验室

LYK 与实验室(lab)
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】
　　0
【数据范围】
　　对于 20%的数据 n,k<=5。
　　对于 40%的数据 n,k<=10。
　　对于 60%的数据 n,k<=500。
　　对于 90%的数据 n,k<=2000。
　　对于 100%的数据 n,k<=5000。

【题目分析】

　　令f[i][j]表示按过i次，当前停留在j层。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

const int mo=1e9+;

using namespace std;

int n,a,b,k;

int f[][];

long long ans=;

int ABS(int x)

{

    return x<?-x:x;

}

int main()

{

    freopen("lab.in","r",stdin);

    freopen("lab.out","w",stdout);

    scanf("%d%d%d%d",&n,&a,&b,&k);

    f[][a]=;

    for(int i=;i<=k;i++)

        for(int j=;j<=n;j++)

            if(j!=b)

                for(int l=;l<=n;l++)

                    if(l!=b&&l!=j)

                        if(ABS(l-j)<ABS(l-b))

                        f[i][j]=(f[i][j]%mo+f[i-][l]%mo),

                        f[i][j]%=mo;

    for(int i=;i<=n;i++)

        if(i!=b)

            ans=ans%mo+f[k][i]%mo;

    cout<<ans%mo;

    fclose(stdin);fclose(stdout);

    return ;

}

考场60无优化

　　那我们考虑哪些层可以到达j层，这些层肯定是一个连续的区间，利用前缀和优化

巴特西

LYK 与实验室

最新文章

热门文章