0w1

Convex Hull Trick

CFR 319 C. Kalila and Dimna in the Logging Industry ( DP, Convex Hull Trick )

Problem - C - Codeforces題意: 有 N 棵樹,用長度 A[ i ] 和魔力 B[ i ] 描述。保證 A 嚴格遞減,B 嚴格遞增,且 A[ 0 ] = 1, B[ N - 1 ] = 0。一次操作選擇一顆長度不為 0 的樹,使之長度少一。每操作完後,必須選擇一棵長度已為 0 的樹的魔力,加到總花…

CFR 631 E. Product Sum ( Convex hull trick DP )

Problem - E - Codeforces pekempeyさんの記事と公式の editorialよりいい解釈はないと思うのでとりあえず。 pekempey.hatenablog.com Editorial Codeforces Round #344 (Div. 2) - Codeforces For this problem, we will consider convex hull trick. There…