val

题目描述

有一个值初始为0，接下来n次你可以令其在之前基础上+2或+1或-1。你需要保证，这个值在整个过程中达到的最大值减去达到的最小值不大于k，求方案数，模1,000,000,007。

输入

仅一行，两个空格隔开的正整数n和k。

输出

仅一行，一个非负整数，表示方案数对1,000,000,007取模后的结果。

样例输入

【输入样例A】

3 2

【输入样例B】

233 99

样例输出

【输出样例A】

11

【输出样例B】

316461264

提示

【评分标准】

对于10%的数据，n,k<=15；

对于30%的数据，n,k<=75；

对于50%的数据，n,k<=300；

对于另10%的数据，k=1；

对于100%的数据，n,k<=5,000。

来源

杭二noip2017模拟3

solution

考场只会n^4Dp，还MLE了

首先我们考虑枚举它的上界，算出下界，然后可以n^2Dp

f[i][j]表示前i次操作，和为j的方案数

if(j-1>=0)f[i][j]=(f[i][j]+f[i-1][j-1])%mod;

if(j-2>=0)f[i][j]=(f[i][j]+f[i-1][j-2])%mod;

if(j+1<=k)f[i][j]=(f[i][j]+f[i-1][j+1])%mod;

然后扣去重复的方案即可。

但这样效率仍然过不去。

我们可以把移动上下界看成移动起点。

初始是把所有点都看成起点，一起计算。

然后可以发现，相邻两点重复方案的计算，与整体是相同的。

那么所有点的重复方案就是0~k-1的Dp值。

效率O（n^2）

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 5005

#define mod 1000000007

using namespace std;

int n,k,f[maxn][maxn];

int main()

{

    cin>>n>>k;

    for(int i=0;i<=k;i++)f[0][i]=1;

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

        for(int j=0;j<=k;j++){

            if(j-1>=0)f[i][j]=(f[i][j]+f[i-1][j-1])%mod;

            if(j-2>=0)f[i][j]=(f[i][j]+f[i-1][j-2])%mod;

            if(j+1<=k)f[i][j]=(f[i][j]+f[i-1][j+1])%mod;

        }

    }

    long long ans=0,aa=0;

    for(int i=0;i<=k;i++)ans=(ans+f[n][i])%mod;

    memset(f,0,sizeof f);

    k--;

    for(int i=0;i<=k;i++)f[0][i]=1;

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

        for(int j=0;j<=k;j++){

            if(j-1>=0)f[i][j]=(f[i][j]+f[i-1][j-1])%mod;

            if(j-2>=0)f[i][j]=(f[i][j]+f[i-1][j-2])%mod;

            if(j+1<=k)f[i][j]=(f[i][j]+f[i-1][j+1])%mod;

        }

    }

    for(int i=0;i<=k;i++)aa=(aa+f[n][i])%mod;

    ans=ans-aa;ans=(ans%mod+mod)%mod;

    cout<<ans<<endl;

    return 0;

}

巴特西

val

val

题目描述

输入

输出

样例输入

样例输出

提示

来源

最新文章

热门文章