CodeForces 425E Sereja and Sets

题意：

集合S中包含许多区间[l,r] 且1<=l<=r<=n f(S)表示该集合最多可以选出多少个不相交的区间 问给出n和f(S) 有几种可能的S集合

思路：

dp好题 至于为啥是dp… 我只能说是胖子大神教我的 - -b

定义 dp[i][j] 表示当n=i且f(S)=j时的S集合种类数 那么它可以通过dp[k][j-1]求得 j-1<=k<=i

可以这样理解转移

首先我们需要将 j-1 -> j 也就是加一个不相交的区间 [k+1,k+1] [k+1,k+2]...都可以 一共有2^(i-k)-1种取法

上式-1因为不能所有这样的区间全不取

为什么不是[k+2,...]的区间呢 因为我是遍历k的 k+2开始的区间在遍历到 k=k+1 的时候会算到

然后 我们可以任意取一些区间 这些区间一定和之前的相交

如何一定相交呢 只要让一端在k以内就好了 因此一共有2^((i-k)*k)种取法

最后得出 dp[i][j] = sigma ( dp[k][j-1] * ( 2^(i - k) - 1 ) * ( 2^( (i - k) * k ) ) ) % mod

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define N 510 #define LL __int64 #define mod 1000000007 LL dp[N][N],f[N*N]; int n,m; int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1,f[0]=1;i