P5464
  • 板块学术版
  • 楼主封禁用户
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/2 20:54
  • 上次更新2023/11/3 08:04:36
查看原帖
P5464
825033
封禁用户楼主2023/11/2 20:54

60分#13~#20 TLE 求助!

#include<iostream>
#include<algorithm>
#define ll long long
#define f(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
const int MAXN=2005,MOD=1e9+7;
int n;
struct Node{
    int x,y;
    bool operator < (const Node& tmp)const{
        return y<tmp.y;
    }
}a[MAXN];
ll dp[MAXN][MAXN];
ll ans;
int main()
{
    int i,j,k;
    cin>>n;
    f(i,1,n){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+1+n);
    f(i,1,n){
        dp[i][0]=1;
        ans++;
        f(j,1,i-1){
            if(a[j].y<a[i].x) continue;
            if(a[j].x<a[i].x){
                f(k,0,j-1){
                    if(a[k].y>=a[i].x) continue;
                    dp[i][j]+=dp[j][k];
                    dp[i][j]%=MOD;
                }
            }
            else{
                f(k,0,j-1){
                    if(a[k].y>=a[j].x) continue;
                    dp[i][j]+=dp[i][k];
                    dp[i][j]%=MOD;
                }
            }
            ans=(ans+dp[i][j])%MOD;
        }
    }
    cout<<ans%MOD<<endl;
    return 0;
}
2023/11/2 20:54
加载中...