主题链接：点击打开链接

意甲冠军：

特定 n a b k

构造一个长度k该序列。

使得序列中 对于随意两个相邻的数 | w[i-1] - w[i] | < | w[i] - b |

且第一个数 |a - w[1] | < | w[1] - b |

问：

有多少种不同的序列。

思路：dp

对于粗暴的dp复杂度是 n^3

我们能够用前缀和来优化掉一维的dp。。

反正是简单粗暴的题。详细看代码吧。。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <queue>

#include <algorithm>

#include <map>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 5005;

const ll mod = 1000000007;

int a, b, K, n;

ll dp[N][N], sum[N];

void put(int k){

    printf("%d:", k);

    for(int i = 1; i <= n; i++)pt(dp[k][i]),putchar(' '); puts("");

}

ll solve(){

    dp[0][a] = 1;

    for(int k = 1; k <= K; k++)

    {

        sum[0] = 0;

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

            sum[i] = sum[i-1] + dp[k-1][i];

            if(sum[i] >= mod) sum[i] -= mod;

        }

        for(int i = 1, j; i <= n; i++)

        {

            if(i==b)continue;

            j = (b+i)>>1;

            if(i < b)

            {

                if(b-j <= j-i) j--;

                dp[k][i] = sum[j] - dp[k-1][i];

            }

            else

            {

                if(j-b <= i-j) j++;

                dp[k][i] = sum[n] - sum[j-1] - dp[k-1][i];

            }

            if(dp[k][i] < 0){

                dp[k][i] %= mod;

                dp[k][i] += mod;

            }

        }

    }

    ll ans = 0;

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

        ans += dp[K][i];

        if(ans >= mod) ans -= mod;

    }

    return ans;

}

int main() {

    while(cin>>n>>a>>b>>K){

        memset(dp, 0, sizeof dp);

        cout<<solve() % mod<<endl;

    }

    return 0;

}