http://vn.spoj.com/problems/NKTICK/

Có N người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ti là thời gian cần thiết để người i mua xong vé cho mình. Nếu người i+1 rời khỏi hàng và nhờ người i mua hộ vé thì thời gian để người thứ i mua được vé cho cả hai người là ri.

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Input

Dòng đầu tiên chứa số N (1 ≤ N ≤ 60000).
Dòng thứ 2 ghi N số nguyên dương t1, t2, …, tN. (1 ≤ ti ≤ 30000)
Dòng thứ ba ghi N-1 số nguyên dương r1, r2, …, rN-1. (1 ≤ ri ≤ 30000)

Output

In ra tổng thời gian phục vụ nhỏ nhất.

Ví dụ

Dữ liệu:
5
2 5 7 8 4
4 9 10 10

Kết qủa
18

Dữ liệu:
4
5 7 8 4
50 50 50

Kết qủa
24

Lần 1: 100đ

Đọc qua ta thấy đây là bài toán tìm phương án tối ưu nên có thể dự đoán ngay là sử dụng quy hoạch động!
Nhìn sơ qua ta có thể dự đoán công thức QHĐ có dạng F[i] với F[i] là thời gian ngắn nhất dành cho i người mua vé, nếu vậy thì kết quả cần tìn là F[n].

Bài toán cơ sở: F[1] = t[1]
Tìm công thức QHĐ:
– Ta đã có F[1], giờ tính F[2], có 2 trường hợp là người thứ 2 này bỏ về nhờ người thứ nhất mua vé (với thời gian là r[1]) hoặc là người đó tự mua vé (với thời gian F[1] + t[2]), kết quả đúng là kết quả nhỏ hơn:
==> F[2] = Min(F[1] + t[2], r[1] )
=> Công thức QHĐ: F[n] = Min(F[n-1] + t[n], r[n-1])
Thử xem sao nhỉ!
à quên r[n-1] chỉ là thời gian của người phía trước mua vé hộ người phía sau thôi, còn phải cộng thêm thời gian phía trước nó nữa là F[n-2] => Bài toán cơ sở cần thêm F[0] = 0 vào.
=> Công thức QHĐ: F[n] = Min(F[n-1] + t[n],F[n-2] + r[n-1])
=> Bài này cơ bản là dễ, làm quen lại với QHĐ.

#include <iostream>

using namespace std;

#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)

typedef long long LL;

int main()
{
	int n;
	cin>>n;
	int F[n+1],t[n+1],r[n];

	FOR(i,1,n)
		cin>>t[i];
	FOR(i,1,n-1)
		cin>>r[i];

	F[0] = 0;
	F[1] = t[1];
	FOR(i,2,n)
		F[i] = min(F[i-1] + t[i],F[i-2] + r[i-1]);

	cout<<F[n]<<endl;

    return 0;
}

Advertisements