CF1256E. Yet Another Division Into Teams 題解 單調隊列優化dp

題目連結：​​https://codeforces.com/contest/1256/problem/E​​

将 \(n\) 個數分成若幹隊，每一隊至少包含 \(3\)

解題思路：

就是比較簡單的單調隊列優化dp，主要是下面這個公式：

​

​f[i] = min(f[j] - a[j+1]) + a[i]​

​

但是因為還有一些額外資料要輸出是以再加一些操作這道題目就解決了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int n, p[maxn], team[maxn], sz[maxn], pres[maxn];
long long f[maxn];
deque<int> que;

struct Node {
    int a, p;
} a[maxn];

bool cmp(Node a, Node b) {
    return a.a < b.a;
}

// f[i] = min(f[j] - a[j+1]) + a[i]

long long cal(int p) {
    return f[p] - a[p+1].a;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a;
        a[i].p = i;
    }
    sort(a+1, a+1+n, cmp);
    for (int i = 3; i <= n; i++) {
        int pre = i - 3;
        if (pre != 1 && pre != 2) {
            while (!que.empty() && cal(que.back()) >= cal(pre)) que.pop_back();
            que.push_back(pre);
        }
        pres[i] = que.front();
        f[i] = cal(que.front()) + a[i].a;
        sz[i] = sz[que.front()] + 1;
    }
    for (int i = n; i; i = pres[i]) {
        for (int j = pres[i]+1; j <= i; j++)
            team[a[j].p] = sz[i];
    }
    cout << f[n] << " " << sz[n] << endl;
    for (int i = 1; i <= n; i++) cout << team[i] << " ";
    return 0;
}