美梦 (fish1)

美梦 (fish1)

测试数据来自 wjszez/1589

【问题描述】
这天晚上,约翰做了个奇怪的美梦。他拥有了分别分布在N座高高低低的山上的N个池塘,N座山连成一条直线,从左往右第i座山的高度是Hi。池塘中的鱼都是他请专家运用科学的方法专门养殖的,为了保护每个池塘的生态环境,他现在要在这N座山上建造若干个看护点。约翰是个很节约的人,在第i座山建造看护点的花费为Ci。假设在第i座山建造一个看护点,则往左或者往右第一座不比这座山低的山将挡住看护的视线。譬如说:
{Hi} = {1 4 4 5 7 2}表示第一座山高度为1,第二座山高度为4。。。
如果在第1座山建造一个看护点,则可以看护第1,2两个池塘。如果在第5座山上建造一个看护点,则左右的池塘都能被看护到。如果在第3座山上建造一个看护点,则能够看护到第2,3,4个池塘。
Problem Task:
要求能够看护到所有的池塘,建造看护点的最小代价是多少。即建造看护点的山对应的花费Ci之和最小。
Problem Input:
第一行包含一个正整数N,N满足1<=N<=1000000。
第二行包含N个正整数,第i个正整数Hi满足1<=Hi<=10^9,表示第i座山的高度
第三行包含N个正整数,第i个正整数Ci满足1<=Ci<=10^9,表示在第i座山建造看护点的代价为Ci
Problem Output:
一行包含一个正整数C,表示最小的代价。
Problem Input Example:
3
1 1 1
2 2 2
Problem output Example:
2

信息

ID
2001
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者