首先发现那个双端队列一定长这样:
也就是说,这个队列中的数先单调递减,然后再单调递增,最小值为 \(1\)。
现在考虑从双端队列中取数,那么当我们取到 \(1\) 这个数时,我们会在原来的双端队列中取到类似这样的两个数列:(分别用红、蓝表示)
那么红、蓝两数列的总长度为 \(k\),剩下的就是绿色的一段,长度为 \(n-k\),我们每次可以从两端任意取,共取 \(n-k-1\) 次,方案数为 \(2^{n-k-1}\)。
所以我们只用考虑前 \(k\) 个数的取法,然后乘上 \(2^{n-k-1}\) 就好了。
由图像,我们看一下弹出序列需要满足什么条件:
-
首先第 \(k\) 位肯定是 \(1\)。(题目要求)
-
前 \(k\) 个数,一定是由一个或两个单调递减的数列混合而成的(这两个数列就是图中的红、蓝两个数列),并且其中的一个单调递减的数列肯定包含 \(1\) 这个点(蓝色数列)。
-
后 \(n-k\) 个数,其最大值应小于某一个提到的单调数列的最小值。也就是绿色段的最大值小于红色段的最小值。
那我们不妨设 \(f(i,j)\) 表示已经取了前 \(i\) 个数,他们的最小值为 \(j\) 时的方案数。(满足上面的 \(3\) 个条件)
那么我们设选的这 \(i\) 个数分成的两个单调递减的序列分别为 \(A\)、\(B\),其中最小值 \(j\) 在 \(A\) 中,\(B\) 中的最小值为 \(minn\)。
设除了我们选的这 \(i\) 个数剩下的 \(n-i\) 个数组成的集合为 \(S\),\(S\) 中最大的数为 \(maxS\)。
大概可以用这张图表示:
由 \(f(i,j)\) 的定义得,\(B\) 序列已经满足了第 \(3\) 个条件,即 \(maxS<minn\)。
我们现在要从 \(S\) 中选一个数,加入 \(A\) 或 \(B\) 里面。
考虑构造:
-
假设加入的数 \(x\) 满足 \(x<j\),那么我们就把它加到 \(A\) 的末尾,此时仍满足所有条件。所以 \(f(i,j)\) 向 \(f(i+1,1)\sim f(i+1,j-1)\) 转移。
-
假设加入的数 \(x\) 满足 \(x\geq j\),如果加入 \(A\) 中,\(A\) 就不满足单调递减的性质了,所以只能加入 \(B\) 中。
然后发现只能把 \(S\) 中的最大值 \(maxS\) 加入到 \(B\) 的队尾(而且必须得满足 \(maxS\geq j\),不然会在第一种情况中算重)。
由于 \(maxS\) 是 \(S\) 中的最大的数,所以当 \(maxS\) 加入 \(B\) 数列成为 \(B\) 数列的最小值后,仍大于 \(S\) 中的所有数,满足条件。
所以 \(f(i,j)\) 向 \(f(i+1,j)\) 转移。
至于为什么 \(S\) 中除 \(maxS\) 的某一个数 \(x\) 都不能加入 \(B\) 的队尾:因为加入后,\(B\) 中的最小值就变成了 \(x\),而 \(S\) 中的最大值仍为 \(maxS\)。此时 \(x<maxS\),不满足条件。
所以通过 \(f(i,j)\) 就可以向 \(f(i+1,1\sim j)\) 转移了。
显然答案就是 \(2^{n-k-1}\times\sum\limits_{i=2}^{n-k+2}f(k-1,i)\)。
还是有很多细节的,详见代码:
#include<bits/stdc++.h>
#define N 2010
#define ll long long
#define mod 1000000007
using namespace std;
int n,k;
ll f[N][N];
ll poww(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=2;i<=n;i++) f[1][i]=1;
for(int i=1;i<k-1;i++)
{
f[i+1][n-i+1]=f[i][n-i+1];
for(int j=n-i;j>=2;j--)
f[i+1][j]=(f[i+1][j+1]+f[i][j])%mod;
}
ll ans=0;
for(int i=2;i<=n-k+2;i++)
ans=(ans+f[k-1][i])%mod;
if(k==1) ans=1;//特判1:k=1
if(n-k-1>=0) printf("%lld\n",ans*poww(2,n-k-1)%mod);
else printf("%lld\n",ans);//特判2:n=k
return 0;
}
标签:数列,maxS,ll,ARC068F,最小值,Solitaire,单调,ans,dp
From: https://www.cnblogs.com/ez-lcw/p/16837090.html