概述
【转载】作者:GuxueAkioi
学习之用,为防丢失,故此转载,万望见谅,若有侵权,联系删除。
题意:一开始有一个长度为 n 的未知排列。给出一个序列 a,其中 a[i] 表示单调栈在第 i 个数入栈后的 size 大小,a[i] = -1 表示 size 大小未知,根据序列 a 输出可能的初始排列的方案数。答案对 1e9+7 取模。
规模:T组数据,T<=20,1<=n<=100。
分析:首先考虑没有-1的情况,根据单调栈的性质我们不难发现最右边的 size==1 的位置其实就是原排列中 1 的位置。将这个位置记为 mid。而找到以后会把原序列分成左右两部分,这两部分中左边的size不变,但是右边的size就要--,因为1已经确定位置了,所以后面能动的数就少了1。然后再到两边找 size==1 的位置分段。这样递归下去,形态就等同一个小根笛卡尔树。因为左右分开以后大小就独立了,所以我们可以从所有数中任选一些数分给左边/右边,方案数即为 C(size,mid-l)。因为分段1次就是O(n),分n次,复杂度O(n^2)。
那么有-1又怎么办呢?其实是一样的,枚举所有的 -1,如果在 mid 左边就不可选,在 mid 右边就可选,然后暴力分段搜。为了保证复杂度,采用记搜,f[l][r][k] 表示区间 [l,r],前面已经分了 k 次段,即我们要在 [l,r] 中找最右边的、大小为 k+1 的继续进行分段。这样定状态就已经可以保证唯一了。然后方案数就是 f[l][r][k]=f[l][mid-1][k]*f[mid+1][r][k+1]*C(r-l,mid-l)。每个状态转移要花 O(n) 的复杂度枚举,所以一共是 O(n^4) 的复杂度,但是因为枚举区间自带大概 1/2 常数,部分状态又转移不到,所以实测跑得飞快。可以对于每个区间 [l,r] 预处理出 mid ,常数大概可以再*1/2,就可以获得和 @nkxjlym 巨佬一样的飞快速度!
总结:发现笛卡尔树模型以后就是简单暴力记搜题,其实难度不大。
#include<bits/stdc++.h>
using namespace std;
const int mo=1000000007;
int n,a[110];
long long f[110][110][110],C[110][110];
long long ddfs(int l,int r,int k)
{
if(f[l][r][k]!=-1) return f[l][r][k];
if(l>r) return f[l][r][k]=1;
if(l==r) return f[l][r][k]=(a[l]==k||a[l]==-1);
f[l][r][k]=0;
int mid=0,len=r-l;
for(int i=r;i>=l;i--)
if(a[i]==k){mid=i;break;}
if(!mid)
{
for(int i=r;i>=l;i--)
if(a[i]==-1)
(f[l][r][k]+=ddfs(l,i-1,k)*ddfs(i+1,r,k+1)%mo*C[len][r-i])%=mo;
}
else
{
for(int i=r;i>mid;i--)
if(a[i]==-1)
(f[l][r][k]+=ddfs(l,i-1,k)*ddfs(i+1,r,k+1)%mo*C[len][r-i])%=mo;
(f[l][r][k]+=ddfs(l,mid-1,k)*ddfs(mid+1,r,k+1)%mo*C[len][r-mid])%=mo;
}
return f[l][r][k];
}
int main()
{
C[0][0]=1;
for(int i=1;i<=100;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
}
int T;
scanf("%d",&T);
while(T--)
{
memset(f,-1,sizeof(f));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
printf("%lldn",ddfs(1,n,1));
}
return 0;
}
最后
以上就是糟糕大树为你收集整理的单调栈(笛卡尔树 区间DP)的全部内容,希望文章能够帮你解决单调栈(笛卡尔树 区间DP)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复