题目描述

社交圈子里有 $[li,ri][l_i,r_i][li,ri]。当两个人的 SAN 值交集不为空时，这两个人有 PY 关系。$

现在希望从社交圈子里面挑选出一些人组成一个集合

请问，有多少种可以选择的方案？由于答案可能很大，请对 $109+710^{9}+7109+7 取模。$

题解

我们首先将这些人的左端点从小到大排序，然后题目要求是要形成一棵树

这样的话，每一个点最多只能被两个区间覆盖，否则就会形成环

考虑dp怎么做，设f[i][j]表示我们从左到右选区间，倒数第二个区间为i，最后一个区间为j的方案数

我们转移的时候枚举j(r[j]<l[i])和k(r[k]<l[j])，就是i和j有交集，k和j有交集，i和k没有交集

动态转移方程为：f[i][j]+=f[j][k]，f[j][i]+=f[j][k]

代码

1 #include 
     
        2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define ll long long 7 using namespace std; 8 const ll N=2010,mo=1e9+7; 9 struct node { ll l,r; }q[N];10 struct Node 11 { 12     ll x,y; 13     bool operator < (const Node &a)const { return x>a.x; }14 };15 priority_queue
          
           Q;16 ll n,ans,bz[N],g[N],f[N][N];17 bool cmp(node x,node y) { return x.l==y.l?x.r>y.r:x.l
           
            q[i].r) f[j][i]+=1+g[j]; else f[i][j]+=1+g[j];35 ans=(ans+1+g[j])%mo;36 }37 }38 printf("%lld",(ans+n)%mo);39 }