主题链接:点击打开链接
意甲冠军:
特定 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;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。