场上想了很久 dp 中的区间左右端点如果当成长度怎么排除在边上不能继续走的影响，后来发现自己是弱智。

首先这种计数题直接往 dp 去想，然后发现正着做要考虑覆盖，十分困难，所以考虑时光倒流，变成一个位置放上之后就不会再改变。

设 $f_{l,r,x,0 / 1}$ 为你的积木区间在 $[l,r]$，$x$ 放置在左端点或者右端点。那么转移是显然的。

我们发现这个 $l,r$ 的真正作用是限制左右转移不出界，那我不管界不就好了？

$f_{x,y}$ 表示积木区间长度为 $x$，最后一个块是 $y$，那么有：

$f_{x,y}\ to f_{x+1,y+1}$

（直接往旁边走）

$f_{x,y}\ to f_{x+1,x+y}$

（走到另一边）

$f_{x,y}\ to f_{x,y+2}$

（来回走，区间长度不会发生变化）

那么一个状态

$f_{x,n / n-1}$

对答案的贡献就是

$2(m-x+1)f_{x,n / n-1}$

（这个 2 是因为我们 dp 的时候没有考虑你最后一个在左边还是右边，另一个系数就是你把这段区间完整的放进最终序列的方案数），代码好写。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=1e9+7,inf=0x3f3f3f3f3f3f3f3f;
const int N=5e3+10,M=2e5+10;
int f[N][N];
int n,m;
inline void add(int &x,int y){x=(x+y)%mod;}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin >> n >> m;
    f[2][2]=1;
    for ( int i = 2 ; i <= m ; i++ )
    {
        for ( int j = 2 ; j <= n ; j++ )
        {
            f[i][j]%=mod;
            add(f[i][j+2],f[i][j]);
            if(j+i<=n)add(f[i+1][j+i],f[i][j]);
            add(f[i+1][j+1],f[i][j]);
        }
    }
    int ans=0;
    for ( int i = 2 ; i <= m ; i++ )
        add(ans,(f[i][n-1]+f[i][n])*(m-i+1)%mod);
    cout << ans*2%mod;
	return 0;
}

比赛结束后听到dp后想了一下，首先想到正着跑， 设计dp[i][j]为把1到i建在k个空地时，i建在第j个空地的情况，一下就想到了那dp[i][j]就等于dp[i-1][j-1]+dp[i-1][j+1]，附上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,mod=1e9+7;
int dp[N][N];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	{
		dp[1][i]=1;
	}
	for(int i=2;i<=n;i++)
	{
		dp[i][1]=dp[i-1][2];
		dp[i][k]=dp[i-1][k-1];
		for(int j=2;j<k;j++)
		{
			dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%mod;
		}
	}
	int ans=0;
	for(int i=1;i<=k;i++)
	{
		ans=(ans+dp[n][i])%mod;
	}
	printf("%d\n",ans);
	return 0;
}

但却27分，仔细一想，发现dp[i-1][j-1]与dp[i-1][j+1]的最终呈现情况可能存在重复，所以不行。

那我们就不妨直接去讨论最终的样子，因为它是后放的覆盖在前放的，所以就反过来想，那么从一种情况到另一种情况就只能是往最左边添加一个更小的数，或是往最右边添加一个更小的数，所以就去枚举原本的最小值。

分别讨论最小值在左右的情况，不妨假设最小值i在最左边,且当前一共有j个数，那么下一种变化如果是在左边，只能是i-1,i-3一直到1或2，如果是在最右边，只能是i-j,i-j-2一直到1或2，反之亦然。所以就直接为别的情况做贡献。

但代码85分TLE，考虑优化，不妨不去做贡献，直接反过来求，因为dp[i][j]是被类似所有的i-1,i-3一直到1或2做贡献，存在单调性，所以可以开前缀和，sum[i][j]记录dp[i][j]+dp[i-2][j]一直到dp[1][j]或dp[2][j]，统一做贡献，但是这题内存较小，就只能中途累加ans，直接将之前的dp拿来当作sum（不要问我怎么知道的。。。）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e3+10,mod=1e9+7;
int dp[N][N][2];
signed main()
{
	int n,k;
	scanf("%lld%lld",&n,&k);
	dp[n-1][2][1]=dp[n-1][2][0]=1;
	int ans=2*(k-2+1)%mod;
	for(int i=n-2;i>=1;i--)
	{
		for(int j=2;j<=min(n-i+1,k);j++)
		{
			dp[i][j][1]=(dp[i+1][j-1][1]+dp[min(i+(j-1),n)][j-1][0])%mod;
			dp[i][j][0]=(dp[i+1][j-1][0]+dp[min(i+(j-1),n)][j-1][1])%mod;
			ans=(ans+(dp[i][j][1]+dp[i][j][0])%mod*(k-j+1)%mod)%mod;
			dp[i][j][1]=(dp[i+2][j][1]+dp[i][j][1])%mod;
			dp[i][j][0]=(dp[i+2][j][0]+dp[i][j][0])%mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}