题解：CF1372E Omkar and Last Floor

Swirl · 2025-12-18 15:23:21 · 题解

事实证明我没有听过 jzp 讲课？

贪心、区间 dp。

题目贡献为 \sum x^2 的形式，考虑贪心，因为 (x + y) ^ 2 > x ^ 2 + y ^ 2 恒成立。故贪心使所有的 1 挤到一起是最优的。于是我们需要考虑的就是「挤」的优先级。

区间 dp，设 f_{l, r} 为 [l, r] 区间内的最大价值。

考虑枚举一个 i \in [l, r] 作为一个「挤」的点，那么 n 个区间中所有包含 i 的区间都应该挤过来，贡献 \left(\sum_{l \le L_j \le i \le R_j \le r} 1\right)^2。接着分开处理 [l, i - 1] 和 [i + 1, r] 两个区间，即 f_{l, i - 1} + f_{i + 1, r}。

方程：

好像可以优化，但是可过，时间复杂度 \mathcal{O}(n^4)。

:::info[code] 实现上，记一个数组代表每个位置的所属区间，再记录每个区间的左右端点即可。

#include <bits/stdc++.h>
//#define fastio
#define int long long
#define bw(x) (1 << x)
#define eb emplace_back
#define pii pair<int, int>
#define inf (0x3f3f3f3f3f3f3f3f)
#define F(x, v) for (auto x : (v))
#define ALL(x) (x).begin(), (x).end()
#define L(i, a, b) for (register int i = (a); i <= (b); ++i)
#define R(i, a, b) for (register int i = (a); i >= (b); --i)
#define FRE(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
using namespace std; bool bgmem;
#ifdef fastio
struct IO {
    #define ion bw(20)
    char i[ion], o[ion], *icl = i, *icr = i, *oc = o;
    char gc() { return (icl == icr && (icr = (icl = i) + fread(i, 1, ion, stdin), icl == icr)) ? EOF : *icl++; }
    void pc(char c) { if (oc - o == ion) fwrite(o, 1, ion, stdout), oc = o; *oc++ = c; }
    void rd(auto &x) { char c; int f = 1; x = 0; while (c = gc(), c < '0' || c > '9') if (c == '-') f = -1; while ('0' <= c && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = gc(); x *= f; } 
    void pr(auto x) { int a[64], p = 0; if (x < 0) x = -x, pc('-'); do a[p++] = x % 10; while (x /= 10); while (p--) pc(a[p] + '0'); } 
    IO& operator>>(char &c) { return c = gc(), *this; }
    IO& operator<<(char c) { return pc(c), *this; }
    IO& operator<<(const char *c) { while (*c) pc(*c++); return *this; }
    IO& operator>>(auto &x) { return rd(x), *this; }
    IO& operator<<(auto x) { return pr(x), *this; }
} io;
#define cin io
#define cout io
#endif
const int N = 105;
inline int cmax(int& x, int c) { return x = max(x, c); }
inline int cmin(int& x, int c) { return x = min(x, c); }
int tes = 1, cas;
namespace zrh {
    int n, m, l[N][N], r[N][N], bl[N][N], dp[N][N];
    void init() {}
    void clear() {}
    void solve() {
        cin >> n >> m;
        L(i, 1, n) {
            int k; cin >> k;
            L(j, 1, k) {
                cin >> l[i][j] >> r[i][j];
                L(s, l[i][j], r[i][j]) bl[i][s] = j;
            }
        }
        L(len, 1, m) L(dl, 1, m - len + 1) {
            int dr = dl + len - 1;
            L(d, dl, dr) {
                int cnt = 0;
                L(e, 1, n) cnt += dl <= l[e][bl[e][d]] && r[e][bl[e][d]] <= dr;
                cmax(dp[dl][dr], dp[dl][d - 1] + dp[d + 1][dr] + cnt * cnt);
            }
        }
        cout << dp[1][m] << "\n";
    }
} bool edmem; signed main() {
    // FRE("", "");
#ifndef fastio
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    // cin >> tes;
    zrh::init(); while (++cas <= tes) zrh::clear(), zrh::solve();
#ifdef fastio
    fwrite(io.o, 1, io.oc - io.o, stdout);
#endif
    // cerr << "time  : " << (double)clock() / CLOCKS_PER_SEC * 1000 << "ms\n";
    // cerr << "memory: " << fabs(&edmem - &bgmem) / 1024 / 1024 << "mb\n";
    return 0;
}
// I will never love zrh again. =(

:::