看我如何用AI把2024年CSP-S真题[染色]P11233 AC的

// P11233 [CSP-S 2024] 染色// 解法：动态规划 + 懒标记优化，O(n log n)，可过 2e5//// 状态设计（核心难点）：//   dp[i][x] = 处理完前 i+1 个数后，与 A[i] 异色的那个颜色，其"最后一个元素的值"为 x 时的最大得分//   约定 x = 0 表示该颜色还没有任何元素（哨兵）。//   理由：只有"异色颜色的最后一个元素"会参与未来的决策（详见转移②），这就是唯一需要保留的历史信息。//// 转移（加入 A[i+1]）：//   ① 同色：A[i+1] 染成与 A[i] 相同的颜色//        dp[i+1][x] = dp[i][x] + (A[i+1]==A[i] ? A[i+1] : 0)      // x 不变//   ② 异色：A[i+1] 染成相反颜色，A[i] 成为新异色颜色的最后一个元素//        dp[i+1][A[i]] = max_x ( dp[i][x] + (A[i+1]==x ? A[i+1] : 0) )//      （A[i+1] 与 A[i] 异色后，它前面最近的同色元素就是原来那个异色颜色的最后元素 x）//// 优化：//   ① 对每个 x 加同一个常数 add -> 全局懒标记 lazy，best[x] 只存相对值//   ② 转移②只需两个量：best[A[i+1]] + A[i+1]  和  max_{x != A[i+1]} best[x]//      -> multiset 按相对值排序，取最大、跳过目标值，O(log n)//   ③ 注意：转移②必须用"转移前"的实际值（old lazy），不能包含本次同色加的 add#include<bits/stdc++.h>using namespace std;using ll = long long;const ll NEG = -(1LL << 60);intmain(){    ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    int T;    cin >> T;    while (T--) {        int n;        cin >> n;        vector<int> a(n);        for (int i = 0; i < n; i++) cin >> a[i];        unordered_map<int, ll> rel;   // 值 -> 相对得分（实际得分 = 相对值 + lazy）        multiset<pair<ll, int>> st;   // (相对值, 值)，按相对值降序取最大        ll lazy = 0;                  // 全局懒标记        rel[0] = 0;                   // 哨兵：异色颜色还没有元素        st.insert({0, 0});        // 取"相对值最大且值 != v"的那个元素的（相对值+old），实际得分；不存在返回 NEG        auto top_except = [&](int v, ll old) -> ll {            while (!st.empty()) {                auto it = prev(st.end());                auto f = rel.find(it->second);                if (f != rel.end() && f->second == it->first) break; // 未过期                st.erase(it);                                        // 过期条目            }            if (st.empty()) return NEG;            auto it = prev(st.end());            while (it != st.begin() && it->second == v) --it;        // 跳过值 == v 的            if (it->second == v) return NEG;                          // 全是 v（不会发生，哨兵 0 永在）            return it->first + old;        };        for (int i = 0; i + 1 < n; i++) {            ll add = (a[i + 1] == a[i]) ? (ll)a[i + 1] : 0;            ll old = lazy;            // 转移前的偏移            lazy += add;              // ① 同色转移：所有状态统一加 add            // ② 异色转移：M = max( best[A[i+1]] + A[i+1], max_{x != A[i+1]} best[x] )（转移前实际值）            ll M = NEG;            auto f = rel.find(a[i + 1]);            if (f != rel.end()) M = max(M, f->second + old + (ll)a[i + 1]);            M = max(M, top_except(a[i + 1], old));            // 写入目标状态：异色后 A[i] 成为异色颜色的最后一个元素            ll nv = M - lazy;         // 转回相对值            auto it = rel.find(a[i]);            if (it == rel.end()) {                rel[a[i]] = nv;                st.insert({nv, a[i]});            } else if (nv > it->second) {                st.erase(st.find({it->second, a[i]}));                it->second = nv;                st.insert({nv, a[i]});            }        }        // 答案 = lazy + 最大相对值        while (!st.empty()) {            auto it = prev(st.end());            auto f = rel.find(it->second);            if (f != rel.end() && f->second == it->first) break;            st.erase(it);        }        cout << lazy + prev(st.end())->first << '\n';    }    return 0;}