Ngày vui của Kaninho

Xem PDF

Điểm: 400 Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Tối hôm qua có lẻ là ngày đầy kỉ niệm và đáng nhớ nhất đối với \(Kaninho\), vì cậu đã nhận được danh hiệu cầu thủ trẻ xuất sắc nhất World Cup 2050, được tổ chức tại Việt Nam, trong niềm hân hoan tột cùng ấy, nhìn những bóng đèn lấp lánh đầy màu sắc, cậu ấy chợt nghĩ ra bài toán và đố \(Henry\) như sau:

Cho \(N\) bóng đèn được đặt tại các tọa độ nguyên \(x_1,x_2,\ldots,x_n\) trên trục số - được làm bằng tre (có chiều dương hướng sang phải). Để làm cho tất cả bóng đèn đều sáng, ông Alexender Anhbơvơ[1] đã thực hiện lần lượt hai bước sau:

  • Bước 1: Chọn một số bóng đèn và bật trực tiếp chúng, và đánh dấu \(∗\) trên mỗi bóng đèn đó. Biết rằng chi phí để bật trực tiếp bóng đèn thứ \(i\)\(c_i\) (\(c_i\) có thể âm)

  • Bước 2: Đối với những chiếc bóng chưa được đánh dấu còn lại, ứng với mỗi chiếc ông sẽ dùng dây dẫn điện để nối nó với chiếc bóng đã được đánh dấu \(∗\) gần nhất bên trái, và chúng mất chi phí chính bằng khoảng cách từ nó đến chiếc bóng gần nhất đó. Nếu không tồn tại chiếc bóng đã được đánh dấu \(∗\) gần nhất bên trái, thì không có cách nào để chiếc đèn đó sáng.

(Chú ý: Ở bước 2, mặc dù các bóng không được đánh dấu \(∗\) đã được nối dây , nhưng ta không được phép đánh dấu \(∗\) lên chúng !)

Gọi \(S\) là tổng chi phí để cho tất cả các đèn được sáng. Tìm giá trị nhỏ nhất có thể của \(S\).

Input

  • Dòng thứ nhất chứa số nguyên \(n \ (1 \leq n \leq 3000)\) - Số bóng đèn.

  • \(n\) dòng tiếp theo, mỗi dòng chứa cặp số nguyên \(x_i, c_i \ (−10^9 \leq x_i,c_i \leq 10^9)\) - Thể hiện tọa độ của bóng đèn thứ \(i\) và chi phí để bật sáng nó trực tiếp

Output

  • In ra giá trị \(S\) cần tìm

Example

Test 1

Input
4
1 2
2 1
3 -1
4 5 
Output
3
Note

  • Bước 1: Ta bật trực tiếp các bóng \(1,2,3\) và đánh dấu \(∗\) lên chúng.

  • Bước 2: Ta nối dây đèn \(4\) với đèn \(3\)

Từ hình vẽ ta có: \(S=2+1+(−1)+(4−3)=3\) là giá trị nhỏ nhất cần tìm.

[1]: Alexender Anhbơvơ (là cậu ruột của Alexender Arnold - là đồng đội của \(Kaninho\) tại \(Liverpool\)), ông là một kĩ sư điện lực lâu năm, sinh ra tại London, nhưng lại sống và làm việc tại Việt Nam. Hiện tại ông đang ở một mình, và là Fan chân chính của Liverpool.


Bình luận


  • 0
    20NguyenLeMinh 11:17 a.m. 18 Tháng 5, 2021

    solve qhd

    include<bits/stdc++.h>

    define fi first

    define se second

    using namespace std ;

    long long n , dp[3005] , d[3005] , f[3005] , t[3005] ;

    pair<long long,long long> a[3005];

    void qhd () {
    sort (a + 1 , a + n + 1 ) ;
    dp[1] = a[1].se ;
    f[1] = dp[1] ;
    t[1] = a[1].fi ;
    for (int i = 2 ; i <= n ; i += 1) {
    dp[i] = min (f[i-1] + a[i].se , dp[i-1] + a[i].se) ;
    t[i] = t[i-1] + a[i].fi ;
    f[i] = dp[i - 1] + (a[i].fi - a[i-1].fi) ;
    for (int j = 1 ; j < i - 1 ; j += 1 ) if(f[i]>dp[j]+t[i]-t[j]-(i-j)a[j].fi) f[i]=dp[j]+t[i]-t[j]-(i-j)a[j].fi;
    }
    cout << min(dp[n] , f[n]) ;
    }

    int main () {
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cin >> n ;
    for (int i = 1 ; i <= n ; i += 1) cin >> a[i].fi >> a[i].se ;
    qhd() ;
    return 0 ;
    }

    1 phản hồi

    • 0
      tuanlinh 2:08 p.m. 25 Tháng 7, 2020

      test VD n=4 mới đúng

      1 phản hồi