Neovim-如何使用编辑器的神

题目

牛牛最近三国演义入了迷，他时常幻想着自己是一代枭雄，坐拥城池百万，精锐无数。

然而他只能做做美梦玩玩三国无双的游戏罢了 qwq。

游戏中牛牛有 $n$ 座城池，城池编号为 1∼$n$，由于某些城池地理位置极其重要，因此牛牛要设置一些关卡来建立防御工程。现在牛牛有 $m$ 个工程计划，每个工程计划有两个整数 $L$,$R$，表示从第$L$座城池到第 $R$座城池中，至少有一个城池被设置为关卡。

牛牛想知道，为了使得每个计划都满足，有多少中不同的设置关卡的方法？

输入

第一行输入两个整数$n$和 $m$，其中 $n$表示城池的数量，$m$表示工程计划的数量。

接下来 $m$ 行，每行两个整数 $L$,$R$，表示该计划要求从第 $L$座城池到第 $R$ 座城池中，至少有一个城池被设置为关卡。

$1 \leqslant n, m \leqslant 10^5, 1 \leqslant L \leqslant R \leqslant n$.

样例

输入：
3 2
2 3
1 2

输出：
5

提示：
用1表示关卡，0表示普通城池，那么这5种方案分别是: 010，011，110，111，101

输入：
12 3
1 7
6 12
5 10

输出：
3988

题解

状态表示: $f(i)$表示只考虑前$i$个城池, 第$i$个城池设置为关卡的所有方案数.

状态计算: 假设$l_i$表示所有右端点小于等于$i$的区间中, 左端点的最大值 (如果所有区间右端点都大于$i$, 那么$l_i = 0$).

那么$f(0) = 0, f(i) = \sum_{j = l_{i-1}}^{i-1}f(j), i \geqslant 0$

代码如下:

最终统计答案时, 答案是$f(l_n) + f(l_n + 1) + … + f(n)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

typedef long long LL;

int n, m;
LL f[N];
int lp[N];


int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        lp[r] = max(lp[r], l);
    }

    f[0] = 1;
    int l = 0;

    for (int i = 1; i <= n; i ++)
    {
        for (int j = l; j <= i - 1; j ++) f[i] = (f[i] + f[j]) % mod;
        l = max(l, lp[i]);

    }

    LL ans = 0;
    for (int i = l; i <= n; i ++) ans = (ans + f[i]) % mod;

    cout << ans << endl;

    return 0;
}

一种优化方法: 前缀和

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

typedef long long LL;

int n, m;
LL s[N];
int lp[N];


int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        lp[r] = max(lp[r], l);
    }

    s[0] = 1;
    int l = 0;

    for (int i = 1; i <= n; i ++)
    {
        if (l > 0) s[i] = s[i - 1] + s[i - 1] - s[l - 1];
        else s[i] = s[i - 1] + s[i - 1];
        l = max(l, lp[i]);

    }

    LL ans = 0;
    if (l > 0) ans = s[n] - s[l - 1];
    else ans = s[n];

    cout << ans << endl;

    return 0;
}