题解：CF1932F Feed Cats

GGapa · 2024-08-10 19:51:18 · 题解

搞不懂你们为啥要搞数据结构，我就很讨厌数据结构，O(n) 就可以解决这道题，代码也非常短。

定义 F(i) 代表 1\sim i 的时间段内最多能够喂的猫的数量，显然需要求的即为 F(n)，考虑到可以预处理数组 S(i) 代表如果在第 i 步投喂，会喂多少只猫，为了避免把一只猫喂死了，我们还需要记录一个数组 mx(i) 代表如果在第 i 步喂猫，最远在多少步不能够再喂，此时已经可以完成这道题，转移方程请详见代码。

using VI = vector<int>;
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)

void solve() {
    int n, m; cin >> n >> m;
    vector<VI> A(n + 1) ;
    vector<int> mx(n + 1), S(n + 2);
    for(int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        mx[x] = max(mx[x], y);
        S[x]++; S[y + 1]--;
    }
    rep(i, 1, n) S[i] += S[i - 1], mx[i] = max(mx[i], mx[i - 1]); 
    vector<int> F(n + 1);
    rep(i, 1, n) {
        F[i] = max(F[i], F[i - 1]);
        F[mx[i]] = max(F[mx[i]], F[i - 1] + S[i]);
    }
    cout << F[n] << '\n';
}