Three displays（贪心）-白红宇

Three displays（贪心）

阅读量：4135 次

发布时间：2019-05-25

本文共 2603 字，大约阅读时间需要 8 分钟。

It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.

There are $ $n$ $ displays placed along a road, and the $ $i$ $-th of them can display a text with font size $ $s_i$ $ only. Maria Stepanovna wants to rent such three displays with indices $ $i < j < k$ $ that the font size increases if you move along the road in a particular direction. Namely, the condition $ $s_i < s_j < s_k$ $ should be held.

The rent cost is for the $ $i$ $-th display is $ $c_i$ $. Please determine the smallest cost Maria Stepanovna should pay.

Input

The first line contains a single integer $

n

$ ($

\le n \le 3\,000

$) — the number of displays.

The second line contains $ $n$ $ integers $ $s_1, s_2, \ldots, s_n$ $ ($ $\le s_i \le 10^9$ $) — the font sizes on the displays in the order they stand along the road.

The third line contains $ $n$ $ integers $ $c_1, c_2, \ldots, c_n$ $ ($ $\le c_i \le 10^8$ $) — the rent costs for each display.

Output

If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices $

i < j < k

$ such that $

s_i < s_j < s_k

Examples

Input

2 4 5 4 10

40 30 20 10 40

Output

Input

100 101 100

2 4 5

Output

-1

Input

1 2 3 4 5 6 7 8 9 10

10 13 11 14 15 12 13 13 18 13

Output

Note

In the first example you can, for example, choose displays $

1

$, $

4

$ and $

5

$, because $

s_1 < s_4 < s_5

$ ($

2 < 4 < 10

$), and the rent cost is $

40 + 10 + 40 = 90

In the second example you can’t select a valid triple of indices, so the answer is -1.

题意：根据第一组序列找一个递增三元组。这个递增三元组对应着三个下面序列的值。求最小的三元组的和。

思想：我们枚举中间一个值，找i前面小于a[i]的最小的值，并且找i后面大于a[i]的最小的值。不断更新最小值。O（n^2）的时间复杂度

代码如下：

#include
   
    #define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxx=3e3+100;int a[maxx],b[maxx];int n;int main(){
   	set
    
      s;	scanf("%d",&n);	for(int i=1;i<=n;i++) scanf("%d",&a[i]);	for(int i=1;i<=n;i++) scanf("%d",&b[i]);	int _max3=inf;	for(int i=1;i<=n;i++)	{
   		int _max1=inf,_max2=inf;		for(int j=1;j
     
      a[i]) _max2=min(_max2,b[j]);		_max3=min(_max3,_max1+_max2+b[i]);	}	if(_max3==inf) puts("-1");	else printf("%d\n",_max3);}

努力加油a啊，(^o)/~

转载地址：http://fytvi.baihongyu.com/

你可能感兴趣的文章