Các học sinh trường THCS X khi lên phòng thực hành trong giờ Tin học rất hay chơi game online. Tiêu biểu là $\color{#00FF00}{\texttt{totand}}$. Để ngăn ngừa $\color{#00FF00}{\texttt{totand}}$ và các học sinh khác cùng chơi, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng trên một chiếc bàn dài, gắn chặt máy xuống mặt bàn rồi đánh số các máy theo thứ tự từ 1 tới N theo chiều từ trái sang phải. $\color{#00FF00}{\texttt{totand}}$ và các học sinh không hề chịu thua, họ quyết định tìm cách nối các máy trên bàn lại bằng các đoạn cáp mạng, sao cho mỗi máy đều được nối với ít nhất một máy khác. Để tiến hành việc này, các học sinh đã tiến hành đo khoảng cách giữa hai máy tính liên tiếp nhau. Yêu cầu: Hãy giúp các bạn học sinh tìm ra cách nối mạng thỏa mãn yêu cầu sao cho tổng độ dài các đoạn cáp nối phải sử dụng là ngắn nhất. + Giải thích xíu nha ucode.vn/problems/noi-mang-44820

Thuật toán

Ta sẽ sử dụng thuật toán Quy hoạch động cho bài này.

Gọi $f(i), g(i)$ lần lượt là tổng độ dài các đoạn cáp nối phải sử dụng ít nhất đối với tất cả các máy từ $1$ đến $i$ nếu nối máy thứ $i$ với máy $i-1$ và ngược lại. Để dễ sử dụng, ta đặt $f(1) = \infty$ (do nối một máy tồn tại với một máy khác không tồn tại sẽ cần vô hạn vật liệu :) ) và $g(1) = 0$

Giả sử ta đã biết được $f(x), g(x)$, và ta cần tính giá trị của $f(x+1)$ và $g(x+1)$ ($1 \leq x < n)$. Ta xét hai trường hợp:

TH1: Nối máy thứ $x+1$ với máy thứ $x$.

Khi đó, ta sẽ chọn một phương án tối ưu hơn trong hai phương án sau:

- Tiếp tục nối máy $x$ với máy $x-1$.

- Không nối máy $x$ với máy $x-1$.

Cả hai trường hợp trên đều đảm bảo máy thứ $x+1$ và máy $x$ luôn được nối với nhau. Do đó, phương án tối ưu trong trường hợp này là $min(f(x), g(x)) + d(x,x+1)$ với $d(x,x+1)$ là khoảng cách giữa máy $x$ và $x+1$.

Do ta đã nối máy $x+1$ với máy $x$ nên ta có phương án tối ưu trong trường hợp này:

$f(x+1) = min(f(x), g(x)) + d(x,x+1)$

TH2: Ngược lại

Lúc này, ta chỉ có thể chọn nối máy thứ $x$ với máy thứ $x-1$ bởi nếu không, máy thứ $x$ sẽ không được nối với bất kỳ máy nào khác. Do đó, phương án tối ưu trong trường hợp này là:

$g(x+1) = f(x)$

Do máy thứ $n$ luôn phải được nối với máy thứ $n-1$ (bởi nếu không thì máy $n$ sẽ không thể được nối với máy nào khác) nên đáp án cần tìm của chúng ta chính là $f(n)$

Code (C++)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 25005;

ll n, df[maxn], dp[2][maxn];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(ll i=1;i<n;i++) cin >> df[i];
    dp[0][1] = 0;
    dp[1][1] = INT_MAX;
    for(ll i=2;i<=n;i++){
        dp[0][i] = dp[1][i-1];
        dp[1][i] = min(dp[0][i-1], dp[1][i-1]) + df[i-1];
    }
    cout << dp[1][n];
}