直接$N^2$ $DP$，就可以了
Subtask 2
用$f[i][j]$表示当前位置为$i$，，结束元素为$j$的方案数。
Subtask 3
看下面
Subtask 4
首先可以枚举一段序列选择同一个重叠的区间，然后一些可以不选，如果选的话要求上升。
然后很容易得到方程，离散化之后就可以$N^4$直接做了。
然后并不会优化，看了题解。
想了想写不出来。
抄代码啦！
#include <map> #include <ctime> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define ll long long #define maxn 505 #define md 1000000007 int n,b[maxn],a[maxn],siz[maxn],ls[maxn*2],top,ans=0,inv[maxn]; int l[maxn],r[maxn],C[maxn],g[maxn],fac[maxn],inv_fac[maxn]; int ksm(int a,int b,int p) {int ret=1;for(;b;a=(ll)a*a%p,b>>=1)if(b&1)ret=(ll)ret*a%md;return ret;} int main() { scanf("%d",&n);fac[0]=1;F(i,1,maxn-1)fac[i]=(ll)fac[i-1]*i%md; inv_fac[0]=1;inv_fac[1]=1;F(i,2,maxn-1) inv_fac[i]=ksm(fac[i],md-2,md); F(i,1,maxn-1) inv[i]=ksm(i,md-2,md); F(i,1,n) scanf("%d%d",&a[i],&b[i]),ls[++top]=a[i],ls[++top]=b[i]+1; sort(ls+1,ls+top+1); top=unique(ls+1,ls+top+1)-ls-1; F(i,1,n) { l[i]=lower_bound(ls+1,ls+top+1,a[i])-ls; r[i]=lower_bound(ls+1,ls+top+1,b[i]+1)-ls; } g[0]=1;C[0]=1; for (int j=1;j<top;++j) { int L=ls[j+1]-ls[j]; for (int i=1;i<=n;++i) C[i]=(ll)C[i-1]*(L+i-1)%md*inv[i]%md; for (int i=n;i>=1;--i) { if (l[i]<=j&&j+1<=r[i]) { int f=0,m=1,c=L; for (int p=i-1;p>=0;--p) { f=(f+(ll)c*g[p]%md)%md; if (l[p]<=j&&j+1<=r[p]) c=C[++m]; } g[i]=(g[i]+f)%md; } } } F(i,1,n) ans=(ans+g[i])%md; printf("%d\n",ans); }
BZOJ 4584 [Apio2016]赛艇 ——动态规划