【AtCoder Regular Contest 068 F】Solitaire | Mrsrz's blog

动态规划。

题目大意：

给你一个双端队列，你要依次将 $1\sim n$ 插入队列。然后将它们都弹出来。问有多少种不同的删除序列，满足第 $k$ 个删除的数是 $1$。

题解：

这个删除序列显然由不超过两个下降子序列组合而成。

我们考虑末尾有连续 $m$ 个数被取了，当前最小的数是 $x$ 且不与 $m$ 个连续。

那么，$x$ 所在的一端后面可以任意取，而另外一端只能取 $n-m$，否则将不满足从小到大插入的条件。

我们按位确定每一位的值。

令 $f_{i,j}$ 表示前 $i$ 个位置确定了，当前的最小的数为 $j$。

如果放在最小的数后面，那么可以转移到 $f_{i+1,t}$（$t\lt j$）。

如果放在另外一端后面，那么可以转移到 $f_{i+1,j}$。

可以用前缀和优化。

取完 $1$ 之后的可以任意删，所以要乘 $2^{n-k-1}$。

时间复杂度 $O(nk)$。

Code：

int f[2003],n,k,ans;
const int md=1e9+7;
int main(){
    __builtin_scanf("%d%d",&n,&k);
    f[n+1]=1;
    for(int i=1;i<k;++i)for(int j=n-i+1;j>1;--j)(f[j]+=f[j+1])%=md;
    for(int i=2;i<=n-k+2;++i)ans=(ans+f[i])%md;
    for(int i=n-k-1;i>0;--i)ans=ans*2%md;
    __builtin_printf("%d",ans);
    return 0;
}