BZOJ2616 SPOJ PERIODNI（笛卡尔树+树形dp）

　　考虑建一棵小根堆笛卡尔树，即每次在当前区间中找到最小值，以最小值为界分割区间，由当前最小值所在位置向两边区间最小值所在位置连边，递归建树。那么该笛卡尔树中的一棵子树对应序列的一个连续区间，且根的权值是这段区间的最小值。

　　在笛卡尔树上跑树形dp。设f[i][j]为在i子树对应棋盘中放j个车的方案数，且棋盘中只考虑这段区间在根的父亲高度上方的部分。转移考虑合并两棵子树再在新增加的矩形部分放车即可，捣鼓一下组合数。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 510

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,a[N],son[N][2],size[N],fa[N],f[N][N],root;

int fac[1000010],inv[1000010];

int build(int l,int r)

{

	if (l==r) {size[l]=1;return l;}

	int mx=l;

	for (int i=l+1;i<=r;i++) if (a[i]<a[mx]) mx=i;

	if (l<mx) son[mx][0]=build(l,mx-1);

	if (mx<r) son[mx][1]=build(mx+1,r);

	fa[son[mx][0]]=fa[son[mx][1]]=mx;

	size[mx]=size[son[mx][0]]+size[son[mx][1]]+1;

	return mx;

}

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int C(int n,int m){if (m>n) return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}

void dfs(int k)

{

	if (son[k][0]) dfs(son[k][0]);

	if (son[k][1]) dfs(son[k][1]);

	for (int i=0;i<=m;i++)

		for (int j=0;j<=i;j++)

		inc(f[k][i],1ll*f[son[k][0]][j]*f[son[k][1]][i-j]%P);

	int h=a[k]-a[fa[k]];

	for (int i=m;i>=0;i--)

		for (int j=min(size[k],i-1);j>=0;j--)

		inc(f[k][i],1ll*f[k][j]*C(size[k]-j,i-j)%P*C(h,i-j)%P*fac[i-j]%P);

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("bzoj2616.in","r",stdin);

	freopen("bzoj2616.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read();

	root=build(1,n);f[0][0]=1;

	fac[0]=1;for (int i=1;i<=1000000;i++) fac[i]=1ll*fac[i-1]*i%P;

	inv[0]=inv[1]=1;for (int i=2;i<=1000000;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;

	for (int i=2;i<=1000000;i++) inv[i]=1ll*inv[i-1]*inv[i]%P;

	dfs(root);

	cout<<f[root][m];

	return 0;

}