f994. 疊疊杯子蛋糕
Tags : DP 動態凸包 斜率優化 李超線段樹
Accepted rate : 9人/11人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-02-24 22:19

Content

小琳想要做杯子蛋糕給小艾吃,於是準備了 $\color{black}{n}$ 個麵團,編號 $\color{black}{1\sim n}$,每個麵團有新鮮度 $\color{black}{a_1\sim a_n}$,和美麗度 $\color{black}{b_1\sim b_n}$。

小琳可以把連續區間的麵團疊起來,做成一個杯子蛋糕,假設選的區間是 $\color{black}{[l,r]}$,則編號 $\color{black}{l}$ 的麵團會被疊在最下面,編號 $\color{black}{r}$ 的麵團會被疊在最上面,越上面的麵團貢獻的新鮮度就會越大。每個杯子蛋糕最後的好吃度除了疊起來的麵團貢獻的新鮮度外,也會加上被前一個杯子蛋糕的美麗度影響的好吃度。

由疊起來的麵團貢獻的好吃度計算如下:最下層的麵團新鮮度可貢獻 $\color{black}{1}$ 倍好吃度,第二層貢獻 $\color{black}{2}$ 倍,最上層貢獻 $\color{black}{r-l+1}$ 倍,所以好吃度總共為 $\color{black}{\sum_{i=l}^{r}(i-l+1)\times a_i}$。

由前一個杯子蛋糕美麗度影響的好吃度計算如下,因為前一個杯子蛋糕最上層麵團的美麗度為 $\color{black}{b_{l-1}}$,所以最後會貢獻 $\color{black}{b_{l-1}\times\sum_{i=l}^{r}a_i}$ 的好吃度,如果前面沒有杯子蛋糕,也就是 $\color{black}{l=1}$,那麼此值可忽略。

一個杯子蛋糕最後的好吃度 $\color{black}{D(l,r)}$ 等於由疊起來的麵團貢獻的好吃度加上前一個杯子蛋糕的美麗度計算後的好吃度,也就是 $\color{black}{D(l,r)=\sum_{i=l}^{r}(i-l+1)\times a_i+b_{l-1}\times\sum_{i=l}^{r}a_i}$。小琳想把所有麵團分成若干個互不重疊的區間,且把這些區間的麵團都疊成杯子蛋糕,每個麵團都會被用到,問最後所有杯子蛋糕好吃度總和最大可以是多少?

就是要你找 $\color{black}{(l_1,r_1)\sim(l_k,r_k),l_1 = 1, r_k = n, r_i+1=l_{i+1}}$,使 $\color{black}{\sum_{i=1}^{k}D(l_i,r_i)}$ 最大。

Input

第一行有一個正整數 $\color{black}{n}$,代表有 $\color{black}{n}$ 個麵團。

第二行有 $\color{black}{n}$ 個整數 $\color{black}{a_1\sim a_n}$,代表 $\color{black}{n}$ 個麵團的新鮮度。

第三行有 $\color{black}{n}$ 個整數 $\color{black}{b_1\sim b_n}$,代表 $\color{black}{n}$ 個麵團的美麗度。

  • $\color{black}{1≤n≤10^6}$
  • $\color{black}{-10^3≤a_i≤10^3}$
  • $\color{black}{-10^9≤b_i≤10^9}$
Output

輸出所有杯子蛋糕的好吃度總和最大可以是多少。

Sample Input #1
5
1 2 3 4 5
1 2 3 4 5
Sample Output #1
55
Sample Input #2
5
-1 -2 -3 -4 -5
1 2 3 4 5
Sample Output #2
-55
Sample Input #3
5
-1 -2 -3 -4 -5
-1 -2 -3 -4 -5
Sample Output #3
25
Sample Input #4
5
1 2 3 4 5
-1 -2 -3 -4 -5
Sample Output #4
55
Sample Input #5
20
-391 784 884 -924 -365 -429 -379 988 445 -381 -464 -908 -173 -846 -912 -643 860 647 180 -181
958978129 78445833 991154106 831306943 -660088085 -9992717 874054816 34873121 954789447 -473259031 692625722 827418239 -868716573 -884911232 -436132937 -582959368 -896777725 -584065635 7739542 567437143
Sample Output #5
4137145811366
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (20%): 3.0s , <1M
公開 測資點#1 (26%): 3.0s , <50M
公開 測資點#2 (27%): 3.0s , <50M
公開 測資點#3 (27%): 3.0s , <50M
Hint :

範例 $\color{black}{1、4}$:把 $\color{black}{1\sim 5}$ 的麵團合在一起可得最大好吃度 $\color{black}{55}$。

範例 $\color{black}{2}$:有多種分法都可使最大好吃度為 $\color{black}{-55}$。

範例 $\color{black}{3}$:把 $\color{black}{5}$ 個麵團變成 $\color{black}{5}$ 個杯子蛋糕,最後好吃度為 $\color{black}{-1 + (-2)(-1) + -2 + (-3)(-2) + -3 + (-4)(-3) + -4 + (-5)(-4) + -5 = 25}$

------------------------------------------

2023/2/24:修正測資並重測。

------------------------------------------

$\color{black}{20\%:n≤10^4}\ $

$\color{black}{80\%:無特別限制}\ $

Tags:
DP 動態凸包 斜率優化 李超線段樹
出處:
第五屆簡單的小競賽 [管理者: becaido (Caido) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」