f995: 疊疊杯子蛋糕 - Extreme
Tags : DP 李超線段樹 樹套樹
Accepted rate : 2人/5人 ( 40% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-17 06:58

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)}\ $ 最大。

喔對了,因為避免吃得太撐,所以每個杯子蛋糕最多只能由 $\color{black}{K}\ $ 個麵團疊成。

Input

第一行有兩個正整數 $\color{black}{n,K}\ $,代表有 $\color{black}{n}\ $ 個麵團,和每個杯子蛋糕最多只能由 $\color{black}{K}\ $ 個麵團疊成。

第二行有 $\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≤K≤n≤3\times 10^5}\ $
  • $\color{black}{-10^3≤a_i≤10^3}\ $
  • $\color{black}{-10^9≤b_i≤10^9}\ $
 
Output

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

Sample Input #1
5 2
1 2 3 4 5
-1 -2 -3 -4 -5
Sample Output #1
-9
Sample Input #2
20 2
-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 #2
3606574445933
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (33%): 3.0s , <10M
不公開 測資點#1 (33%): 3.0s , <10M
不公開 測資點#2 (34%): 3.0s , <10M
Hint :

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

Tags:
DP 李超線段樹 樹套樹
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
29368 becaido(Caido) f995
題解
8377 2022-02-18 23:30