P5464 缩小社交圈 题解

· · 题解

这道题，一开始觉得是图论有关的。。。。

嗯。。。我们可以发现，建出来的树一定是一条链带上几个大小为1的节点(这些

节点就是被包含的)。

一开始想的非常复杂，设了5维dp[i][j][k][p][o]表示大小为i，最左的左

端点的点为j,次左的左端点的点为k，最右的点为p,次右的为o。于是对于

两条链，我们合并其大小，以次左，最左，次右，最右为判断条件进行合并。但是

我们会猛然发现，我们没有必要两条链进行合并，直接枚举一个区间，看能否结合

于是我们可以减少掉大小，左和次左三个维度。

所以复杂度为O(n^3)

最后我们前缀和优化一下就行。

#include<bits/stdc++.h>

using namespace std ;

#define N 3000
const int Mod = 1e9 + 7 ;

inline int read()
{
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') { c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

int n ;
int dp[N][N] , sum[N][N] , pre[N] ;

struct node{
    int L , R ;
}A[N] ;

bool operator < ( node a , node b ){ return a.R < b.R ; }

int main()
{
    n = read() ;

    for(int i = 1 ; i <= n ; i++ ) A[i].L = read() , A[i].R = read() ;
    sort( A + 1 , A + n + 1 ) ;

    for(int i = 1 ; i <= n ; i++ ){
        pre[i] = 0 ;
        for(int j = i - 1 ; j >= 1 ; j-- ){
            if( A[j].R < A[i].L ){
                pre[i] = j ;
                break ;
            }
        }
    }
    for(int i = 1 ; i <= n ; i++ ){
        for(int j = 1 ; j <= i - 1 ; j++ ){
            if( A[j].R < A[i].L ){
                sum[i][j] = sum[i][j - 1] ;
                continue ;
            }
            if( A[i].L > A[j].L ){
                //for(int k = 1 ; k <= j - 1 ; k++ ){ if( A[k].R < A[i].L ) dp[i][j] = ( dp[i][j] + dp[j][k] ) % Mod ; }
                dp[i][j] = 1 + sum[j][ pre[i] ] ;
            }else{
                //for(int k = 1 ; k <= j - 1 ; k++ ) if( A[k].R < A[j].L ) dp[i][j] = ( dp[i][j] + dp[i][k] ) % Mod ;
                dp[i][j] = 1 + sum[i][ pre[j] ] ;
            }
            if( dp[i][j] >= Mod ) dp[i][j] -= Mod ;
            sum[i][j] = dp[i][j] + sum[i][j - 1] ;
            if( sum[i][j] >= Mod ) sum[i][j] -= Mod ;
        }
    }
    int ans = 0 ;
    for(int i = 1 ; i <= n ; i++ ){
        ans = ans + sum[i][i - 1] ;
        if( ans >= Mod ) ans -= Mod ;
    }
    printf("%d\n" , ( ans + n ) % Mod ) ;

    return 0 ;
}