题目大意：
我们有一个集合 S，其中包含了 m 个不完全相同的区间[l1,r1]，[l2,r2]…[lm,rm] （1≤li≤ri≤n，li,ri 都为整数）。
定义 f(S)=k，表示集合 S 中能取出最多 k 个区间，使得这 k 个区间两两不相交。 问当 f(S)=k 时，符合条件的集合 S 有多少个。
思路：
f[i][j]表示集合S中所有区间的端点均小于等于i且f(S)=j的集合S的个数。
显然i≥j，则f[i][j]由f[k][j-1](j-1≤k≤i)转移而来，新的与之前区间不相交的区间的起点为k+1，k+1≤终点≤i，则有2i-k-1种选择出有且仅有一个区间与之前的区间不相交即有用区间（k+1为起点，有i-k个与之前的区间不相交，任取其中的多个或一个），而多出的无用区间即与之前的相交的区间的两个端点一个小于等于k一个大于k，则有(i-k)*k个，任取，有2(i-k)*k种，所以转移方程为f[i][j]=∑(f[k][j-1]*(2i-k-1)*2(i-k)*k)。
代码：
1 #include<cstdio> 2 #define mo 1000000007 3 long long mi[62501],f[501][501]; 4 int i,j,k,n,m; 5 6 int main() 7 { 8 scanf("%d%d",&n,&m),k=n*n>>2; 9 for (mi[0]=i=1;i<k+2;++i) 10 if ((mi[i]=mi[i-1]<<1)>=mo) mi[i]-=mo; 11 for (i=0;i<=n;++i) f[i][0]=1; 12 for (i=1;i<=n;++i) 13 for (j=1;j<=i;++j) 14 for (k=j-1;k<=i;++k) 15 f[i][j]=(f[i][j]+f[k][j-1]*(mi[i-k]-1)%mo*mi[(i-k)*k])%mo; 16 printf("%lld\n",f[n][m]); 17 return 0; 18 }
转载于:https://www.cnblogs.com/HHshy/p/6371063.html
