Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11KM - Khuyến mãi

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


Được gửi lên bởi:Nguyễn Duy Khánh
Ngày:2011-12-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Sưu tầm

hide comments
2017-12-11 02:45:36 hồ vãn tuấn
dùng khuyến mãi để mua thì có được khuyến mãi không nhỉ
2017-09-02 06:49:08
mình dùng tham lam bị sai test này:
4
101 99 101 99
Để lại cho mấy bạn làm sau
2017-08-22 17:34:37
Em không đc AC mà không biết tại sao luôn test max đề hay gì đều đúng cả mà có test nào hiểm sao T.T
2017-07-13 09:41:14
for (int i=0;i<=d[n];i++)
minres=min(minres,f[n][i]); // AC
if (i==n) minres=min(minres,f[i][j]);// 0d
2017-06-14 11:59:46
vl ong ben duoi =))
2017-04-08 05:35:51
#include <bits/stdc++.h>

using namespace std;
long long tong,i,a[10000],f[2000][2000],d[10000],j,n,ma,t;
int main()
{
//freopen("t.inp","r",stdin);
//freopen("t.out","w",stdout);
cin>>n;tong=0;ma=1e18;
for (i=1;i<=n;i++) cin>>a[i];
for (i=1;i<=n;i++)
{ tong=tong+a[i];d[i]=d[i-1];
for (j=0;j<=d[i];j++)
{
if (d[i]>j) f[i][j]=min(f[i-1][j+1],f[i-1][j]+a[i]);
else f[i][j]=tong;
}
if (a[i]>100)

{
d[i]++;f[i][d[i]]=tong;
for (t=1;t<d[i]-1;t++) f[i][t]=min(f[i-1][t-1]+a[i],f[i-1][t+1]);
if (d[i]>1) f[i][d[i]-1]=min(f[i][d[i]-1],f[i-1][d[i]-2]+a[i]);
}
}
for (i=0;i<=d[n];i++) ma=min(ma,f[n][i]);
cout<<ma<<endl;
//for (i=1;i<=n;i++)
//{for (j=0;j<=d[i];j++) cout<<f[i][j]<<" ";cout<<endl;}
return 0;
}
2017-03-20 04:57:52


Last edit: 2017-03-20 05:02:10
2017-03-20 04:56:28
hoangducsmagic

Last edit: 2017-03-20 04:57:30
2016-11-02 16:24:40
Code Pascal:
http://shink.in/ASO0D
2016-10-19 19:31:15
p[i] <=300 n <=1e3 kia mà long long nỗi gì nhỉ ??????
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.