题目描述

blablabla

样例

blablabla

算法1

(主席树优化dp) $O(n^2k)$

$f[i][j]$ 表示前$i$个数, 分$j$段的最小值

则转移函数为$f[i][j] = min(f[q][j - 1] + cost[q + 1][i])$

问题变成了求区间的贡献

有仓货选址可知, 要选择区间的中位数

那么怎么求区间中位数并计算贡献呢

当然是主席树啦, 求中位数的时候顺便就求了贡献了

不吸氧11s也能过, 吸氧3s多

时间复杂度

参考文献

C++ 代码

struct BIT {
    struct node { int val, sum, l, r; } tr[N * 15];
    int rt[N], tot;
    void update(int& x, int y, int l, int r, int d, int k, VI& c) {
        tr[x = ++tot] = tr[y]; tr[x].val += k, tr[x].sum += c[d] * k;
        if (l == r) return;
        int mid = l + r >> 1;
        if (mid >= d) update(tr[x].l, tr[y].l, l, mid, d, k, c);
        else update(tr[x].r, tr[y].r, mid + 1, r, d, k, c);
    }
    int ask(int x, int y, int l, int r, int k, int s, int len, VI& c) {
        if (l == r) return s - c[l] * len;
        int mid = l + r >> 1, val = tr[tr[x].l].val - tr[tr[y].l].val;
        if (val >= k) return ask(tr[x].l, tr[y].l, l, mid, k, s + tr[tr[x].r].sum - tr[tr[y].r].sum, len + tr[x].val - tr[y].val - val, c);
        else return ask(tr[x].r, tr[y].r, mid + 1, r, k - val, s - tr[tr[x].l].sum + tr[tr[y].l].sum, len - val, c);
    }
} bit;

int n, m, _, k, cas;
ll f[N][26], a[N], co[N][N];

int main() {
    IOS;
    while (cin >> n >> k, n || k) {
        rep(i, 2, n) rep (j, 1, k) f[i][j] = 1e18;; VI c(1, -1e9);
        rep(i, 1, n) bit.rt[i] = 0, cin >> a[i], c.pb(a[i]); bit.tot = 0;
        sort(all(c)); c.erase(unique(all(c)), c.end());
        rep(i, 1, n) a[i] = lower_bound(all(c), a[i]) - c.begin(),
            bit.update(bit.rt[i], bit.rt[i - 1], 1, c.size() - 1, a[i], 1, c);
        rep(i, 1, n) rep(j, i, n)
            co[i][j] = bit.ask(bit.rt[j], bit.rt[i - 1], 1, c.size() - 1, j - i + 2 >> 1, 0, 0, c);
        rep(i, 1, n - k + 1) f[i][1] = co[1][i];
        rep(i, 2, n) per(j, min(i, k), 2) rep(q, j - 1, i - 1)
            umin(f[i][j], f[q][j - 1] + co[q + 1][i]);
        cout << f[n][k] << '\n';
    }
    return 0;
}