Skip to content

1460: 小V的区间

题目

题目描述

小V最近在研究一种很有价值的区间

它的具体形式如下:

对于一个[1,N]的区间来说,它的价值为把它划分成若干个(≥ 1 个)区间后,各个子区间(闭区间)的value之和的最大值。

一个区间[L,R]的value定义为 A[R]*∑(C[i]),L<=i<=R (A,C为给定的序列)

现在小V想请你帮忙,求出给定A,C序列后的区间[1,N]的价值

输入格式

第 1 行,一个正整数 N,表示区间[1,N]。

第 2 到 N+1 行,每行两个数 C[i]和 A[i]。

输出格式

输出一个数,表示价值

样例输入

5

1 5

2 2

3 1

4 4

5 2

样例输出

51

数据范围

对于 30%的数据,N<=10;

对于 60%的数据,N<=1000;

对于 100%的数据,N<=100000,0<=C[i]<1000,0<=A[i]<1000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!