一直零分,求调
查看原帖
一直零分,求调
415773
OIer_ACMer楼主2024/7/20 23:53
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int n, m;
int gg[10009];
int sum[4009][4009];
struct node
{
    int l, r;
} san[10009];
bool cmp(node a, node b)
{
    if (a.r != b.r)
    {
        return a.r < a.r;
    }
    return a.l > b.l;
}
int ans = 0;
signed main()
{
    cin >> n;
    // m = read();
    for (int i = 1; i <= n; i++)
    {
        cin >> san[i].l >> san[i].r;
    }
    sort(san + 1, san + n + 1, cmp);
    // for (int i = 1; i <= n; i++)
    // {
    //     cout << san[i].l << ' ' << san[i].r << endl;
    // }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            // cout << gg[i] << endl;
            if (san[j].r < san[i].l)
            {
                gg[i] = j;
            }
            else
            {
                break;
            }
        }
    }
    // for (int i = 1; i <= n; i++)
    // {
    //     cout << gg[i] << endl;
    // }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        sum[i][0] = 1;
        for (int j = 1; j < i; ++j)
        {
            if (san[j].r >= san[i].l)
            {
                if (san[j].l < san[i].l)
                {
                    // cout << "sum[" << i << "][" << j << "]=" << sum[i][j] << endl;
                    sum[i][j] = (sum[i][j] + sum[j][min(j - 1, gg[i])]) % MOD; // 如果有一部分漏在外面
                    // cout << "gggsum[" << i << "][" << j << "]=" << sum[i][j] << endl;
                }
                else
                {
                    sum[i][j] = (sum[i][j] + sum[i][min(j - 1, gg[j])]) % MOD; // 如果已经包含
                }
            }
            sum[i][j] = (sum[i][j] + sum[i][j - 1]) % MOD; // 更新前缀和
        }
        ans = (ans + sum[i][i - 1]) % MOD;
    }
    cout << ans % MOD << endl;
    return 0;
}

2024/7/20 23:53
加载中...