http://acm.hdu.edu.cn/showproblem.php?pid=5181
题意：
有一个栈，其中有n个数1~n按顺序依次进入栈顶，在某个时刻弹出。
其中m个限制，形如数字A必须在数字B之前弹出。
求方案总数
dp[i][j]表示数字i~j的出栈方案数
枚举最后一个出栈的数k，若k合法
dp[i][j]+=dp[i][k]*dp[k+1][j]
如何判断k是否合法？
对于一组i，j，k来说，它的弹出顺序是 [i,k-1]早于[k+1,j]早于k
对于一个限制 A必须在B之前出栈
它只会对 i<=min(A,B),j>=max(A,B) 的 dp[i][j] 产生影响
若A<B，
a、i<=k<A或B<k<=j，产生的影响已在子DP中求出
b、k=A，A最后出栈，显然不合法
c、k=B，B最后出栈，显然合法
d、A<k<B，[A,k-1]早于[k+1,B]早于k出栈，所以合法
若B<A，
a、i<=k<B或A<k<=j，产生的影响已在子DP中求出
b、k=A，A最后出栈，显然不合法
c、k=B，B最后出栈，显然合法
d、B<k<A，[B,k-1]早于[k+1,A]早于k出栈，所以不合法
综上所述
对于一个限制A必须在B之前出栈
若A<B，当k=A时不合法
若B<A，当k∈(B,A]时不合法
这样的话之间复杂度时O（n^3 * m）
对于限制A必须在B之前出栈，如果确定了不能用k转移
考虑这些区间有哪些
令mi=min（A，B），mx=max（A，B）
那么区间
[1,mx] [1,mx+1] [1,mx+2]……[1,n]
[2,mx] [2,mx+1] [2,mx+2]……[2,n]
……
[mi][mx] [mi,mx+1] [mi,mx+2]……[mi,n]
不能用k转移
如果把这些区间的左右端点当做二维平面上的一个点对
那么这些区间就是 以[1,mx]为左上角，以[mi,n]为右下角的一个矩形
那么对于每个k，利用差分和前缀和预处理出这些矩形，就可以做到O（1）查询k转移dp[l,r]是否合法
时间复杂度为O（n^3 + nm）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; const int mod=1e9+; #define N 302
#define M 90001 int n,m; int lim[M][]; int a[N][N][N]; int dp[N][N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int xl,int yl,int xr,int yr,int k)
{
a[xl][yl][k]++;
a[xl][yr+][k]--;
a[xr+][yl][k]--;
a[xr+][yr+][k]++;
} void pre()
{
memset(a,,sizeof(a));
int mi,mx;
for(int i=;i<=m;++i)
{
mi=min(lim[i][],lim[i][]);
mx=max(lim[i][],lim[i][]);
if(lim[i][]<lim[i][]) add(,mx,mi,n,lim[i][]);
else
for(int j=lim[i][]+;j<=lim[i][];++j) add(,mx,mi,n,j);
}
for(int k=;k<=n;++k)
{
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
a[i][j][k]=a[i-][j][k]+a[i][j-][k]-a[i-][j-][k]+a[i][j][k];
}
} void DP()
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;++i) dp[i][i]=;
for(int i=;i<=n+;++i) dp[i][i-]=;
for(int i=n-;i;--i)
for(int j=i+;j<=n;++j)
for(int k=i;k<=j;++k)
if(!a[i][j][k])
dp[i][j]=(dp[i][j]+(long long)dp[i][k-]*dp[k+][j])%mod;
cout<<dp[][n]<<'\n';
} int main()
{
int T;
read(T);
bool tag;
while(T--)
{
read(n); read(m);
tag=true;
for(int i=;i<=m;++i)
{
read(lim[i][]),read(lim[i][]);
if(lim[i][]==lim[i][]) tag=false;
}
if(!tag) { puts(""); continue; }
pre();
DP();
}
}