自动搬运

查看原文

来自洛谷，原作者为

	Regimes 这个家伙AFO了，什么也没有

搬运于2025-08-24 22:11:02，当前版本为作者最后更新于2019-07-16 20:38:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

嗯。。。我们可以发现，建出来的树一定是一条链带上几个大小为$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 ;
}