C11KM - Khuyến mãi - Solution for SPOJ

Problem

https://vn.spoj.com/problems/C11KM

https://oj.vnoi.info/problem/C11KM

Siêu thị Songuku95 mở một cuộc siêu khuyến mãi nhằm khuyến khích người tiêu dùng mua hàng.

Siêu thị khuyến mãi N ngày. Mỗi ngày chỉ bán 1 sản phẩm cho mỗi người có giá là p[i] , tuy nhiên nếu p[i] > 100 thì khách hàng sẽ nhận đc 1 thẻ khuyễn mãi mua 1 món hàng miễn phí với bất cứ giá nào ở các ngày sau:D

Acer_ nhân cơ hội này quyết mua tất cả các mặt hàng ở mỗi ngày, đơn giản vì nhà có điều kiện :> đại gia =)) Dù đại gia nhưng Acer_ vẫn muốn tích kiệm tối đa ( giàu mà ki :”3 )

Tìm tổng số tiền mà Acer_ phải trả

Input

Dòng 1 : N (n <= 10^3)
N dòng tiếp theo mỗi dòng chứa 1 số nguyên dương p[i] <= 300

Output

In ra số tiền phải trả ít nhất

Example

Input
5
35
40
101
59
63

Output
235

Tutorial

Gọi F[i][j] là giá tiền nhỏ nhất khi thanh toán hết i món hàng đầu tiên (mua hoặc lấy) và còn j lần lấy. Ban đầu F[i][j] = oo và F[0][0] = 0.

Xét đến món hàng thứ I thì có hai trương hợp :

Thứ nhất là a[i] > 100 : có hai cách thanh toán : nếu lấy thì F[i][j] = F[i-1][j+1]. Còn nếu mua thì F[i][j] = F[i-1][j-1]+a[i]

Thứ hai là a[i] <= 100 : có hai cách thanh toán : nếu lấy thì F[i][j] = F[i-1][j+1]. Còn nếu mua thì F[i][j] = F[i-1][j-1]+a[i].

Ở cả hai trương hợp đều lấy min cho kết quả. Kết quả bài toán là min(F[n][i]) với i = 0->n. Do trong công thức tính F[i][j] có ảnh hưởng bởi F[i-1][j+1] nên phải khởi tạo mảng F[i][j] với 0<=i<=n+1 và 0<=j<=n+1.

Submission

C11KM.cpp

Tutorial SPOJ

C11KM - Khuyến mãi