TIOJ 1961：[IOI 2016] Aliens

TIOJ 1961：[IOI 2016] Aliens

題目大意：有一個 $m\times m$ 的平面與 $n$ 個格子，第 $i$ 個格子的座標是 $(x_i,y_i)$，可以在一個正方形的區域拍照，並且這個正方形其中一個對角線是 $y=x$，要在剛好 $k$ 次拍照蓋住 $n$ 個格子，並讓有被拍到的格子數越小越好。

解法：Aliens 優化的名稱由來。

令 $l_i=\min(x_i,y_i),r_i=\max(x_i,y_i)+1$，這個格子會被拍到相當於要有線段包住 $[l_i,r_i)$，把這些線段排序一下，並把被其他線段包住的線段丟掉，滿足 $l_i<l_{i+1},r_i<r_{i+1}$，列出 $dp$ 式：$dp_i  = \min(dp_j + (r_i-l_{j+1})^2 - \max(0,r_j-l_{j+1})^2)$，發現可以斜率優化，但是要做 $k$ 次。

因為題目名稱是 Aliens，所以可以考慮 Aliens 優化，二分搜一個 $\text{penalty}$，$M_j=-2l_{j+1},K_j=dp_j+l_{j+1}^2 - \max(0,r_j-l_{j+1})^2,x_i=r_i,C_i=r_i^2$，$dp$ 式可以寫成 $dp_i=\min(M_j\times x_i+K_j)+C_i+\text{penalty}$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#pragma GCC target("sse,sse2,sse3,ssse3,abm,avx2")
#include <bits/stdc++.h>
#include "lib1961.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, k;
pair<int, int> p[SIZE];

pair<ll, int> dp;
deque<tuple<int, ll, int>> st;
pair<ll, int> cal(tuple<int, ll, int> f, int x) {
    return {1ll * get<0>(f) * x + get<1>(f), get<2>(f) + 1};
}
bool del(tuple<int, ll, int> L1, tuple<int, ll, int> L2, tuple<int, ll, int> L) {
    auto [M1, K1, c1] = L1;
    auto [M2, K2, c2] = L2;
    auto [M, K, c] = L;
    return make_pair((K - K1) * (M1 - M2), c) <= make_pair((K2 - K1) * (M1 - M), c2);
}
bool ok(ll pen) {
    st.clear();
    st.pb(-2 * p[1].F, 1ll * p[1].F * p[1].F, 0);
    FOR (i, 1, n) {
        while (st.size() >= 2 && cal(st[0], p[i].S) >= cal(st[1], p[i].S)) st.pop_front();
        dp = cal(st[0], p[i].S);
        dp.F += 1ll * p[i].S * p[i].S + pen;
        if (i == n) break;
        tuple<int, ll, int> val = {-2 * p[i + 1].F, dp.F + 1ll * p[i + 1].F * p[i + 1].F - (p[i].S > p[i + 1].F ? 1ll * (p[i].S - p[i + 1].F) * (p[i].S - p[i + 1].F) : 0), dp.S};
        while (st.size() >= 2 && del(st.end()[-2], st.back(), val)) st.pop_back();
        st.pb(val);
    }
    return dp.S <= k;
}

ll take_photos(int _n, int m, int _k, int _r[], int _c[]) {
    n = _n, k = _k;
    FOR (i, 0, n - 1) {
        if (_r[i] > _c[i]) swap(_r[i], _c[i]);
        p[i + 1] = {_r[i], _c[i] + 1};
    }
    sort(p + 1, p + n + 1, [&](auto l, auto r) {
        return l.F != r.F ? l.F < r.F : l.S > r.S;
    });
    int sz = 0;
    FOR (i, 1, n) if (sz == 0 || p[i].S > p[sz].S) p[++sz] = p[i];
    n = sz;
    ll l = 0, r = 1ll * m * m;
    while (l < r) {
        ll mid = (l + r) / 2;
        if (ok(mid)) r = mid;
        else l = mid + 1;
    }
    ok(l);
    return dp.F - 1ll * k * l;
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！