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

Overview

NKCABLE - Nối mạng

solution.md

Gọi \(f(i)\) là độ dài cáp cần nối cho máy từ 1 đến \(i\). Ta có công thức:

  • \[f(0) = 0\]
  • \[f(1) = \infty\]
  • \[f(i) = \mathrm{min}(f(i-1), f(i-2)) + a(i)\]

Với \(a(i)\) là khoảng cách từ máy \(i-1\) đến máy \(i\).

main.cpp
Open in Github • Download 
#include <iostream>
using namespace std;

const long long oo = 1ll << 62;

int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n; cin >> n;
    long long f0 = 0, f1 = oo, f2;
    for (; n > 1; n--) {
        int x; cin >> x;
        f2 = min(f0, f1) + x;
        f0 = f1;
        f1 = f2;
    }
    cout << f1 << endl;
}
Comments