Ngày vui của Kaninho
Xem PDFTố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\) là \(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
3Note
-
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
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 ;
}
-
0
giangcbg
1:03 p.m. 18 Tháng 5, 2021
1 bình luận nữathích pay acc r :))