let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

HIREHP - Cho thuê xe

solution.md

Gọi \(f_i\) là chi phí ít nhất để có xe đi từ ngày 1 đến hết ngày \(i\). Ta có công thức tính:

\[f_0 = 0\\ f_i = min\{f_{j-1} + p_j \mid j \in [1, i], t_j \geq i\}\]

Ta dùng heap để giảm độ phức tạp về \(O(n\log n)\) như đoạn code bên dưới. Cụ thể như sau:

  • Heap lưu các cặp \((f_{j-1} + p_j, t_j)\).
  • Ở mỗi bước, trước khi tính \(f_i\), ta loại các phần tử có \(t_j < i\) ra khỏi heap. Lưu ý là ta chỉ quan tâm tới các phẩn tử ở đỉnh heap, nên những phần tử có \(t_j < i\) nhưng không ở đỉnh heap thì không cần xóa.

Xem code để biết thêm chi tiết.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define LL long long

struct pack { LL f; int t; };
bool operator > (pack a, pack b) {
    return a.f > b.f;
}
typedef priority_queue<pack, vector<pack>, greater<pack>> min_heap;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> t(n+1);
    vector<LL> p(n+1);
    for (int i=1; i<=n; i++) cin >> t[i] >> p[i];

    // Ở đây dùng mảng f để cho rõ nghĩa
    // Có thể dùng một biến long long f mà thôi.
    vector<LL> f(n+1, 0);
    min_heap heap;
    for (int i=1; i<=n; i++) {
        heap.push({f[i-1] + p[i], t[i]});
        while (!heap.empty() && heap.top().t < i) heap.pop();
        f[i] = heap.top().f;
    }

    cout << f[n];
    return 0;
}
Comments