A. E51*【斜率优化】打印文章[HDU3507]

    传统题 1000ms 512MiB

E51*【斜率优化】打印文章[HDU3507]

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

给出 NN 个非负整数 CiC_i,将它们分成连续的若干段,每段的费用为此段和的平方,还要加一个常数 LL,即 (Ci)2+L(\sum C_i)^2+L

现在想求出一种最优方案,使得总费用之和最小。

【输入格式】

包含多组测试数据,对于每组测试数据:

第一行包含两个整数 NNLL

第二行为 NN 个整数。

【输出格式】

输出仅一个整数,表示总费用的最小值。

5 5
5 9 5 7 5
230

【数据范围与提示】

对于全部数据,0N5×105,0Ci,L10000\le N\le 5\times 10^5, 0 \le C_i,L \le 1000

课堂测试(20250615)斜率优化入门3题

未参加
状态
已结束
规则
XCPC
题目
3
开始于
2025-6-15 9:55
结束于
2025-6-15 11:40
持续时间
1.8 小时
主持人
参赛人数
12