仍然是算导风格的学习笔记
P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
P 教授有编号为 \(1 \cdots n\) 的 \(n\) 件玩具，第 \(i\) 件玩具经过压缩后的一维长度为 \(C_i\)。
为了方便整理，P 教授要求：
-
在一个一维容器中的玩具编号是连续的。
-
同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 \(i\) 件玩具到第 \(j\) 个玩具放到一个容器中，那么容器的长度将为 \(x=j-i+\sum\limits_{k=i}^{j}C_k\)。
制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 \(x\)，其制作费用为 \((x-L)^2\)。其中 \(L\) 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 \(L\)。但他希望所有容器的总费用最小。
数组下标均从 \(0\) 开始。
-
设计一个 \(O(n^2)\) 的算法解决此问题。（提示：动态规划。）
-
考虑第 \(i(i \ge 2)\) 个物品之前的两个物品 \(j,k(j \lt k)\)，何时从 \(k\) 转移至 \(i\) 优于从 \(j\) 转移至 \(i\)？（提示：表达式应只与 \(i,j,k\) 有关，而与它们之间的其他数无关；你可以预处理出一些数组。）
-
将上一问中的表达式变形为关于 \(\dfrac{f(k)-f(j)}{g(k)-g(j)}\) 的不等式，其中 \(f\) 和 \(g\) 可以自由设定。
-
考虑点 \((g(k), f(k))\) 和 \((g(i), f(i))\)，上一问的不等式有什么几何意义？
-
设计一个 \(O(n)\) 的算法解决此问题。（提示：在线地维护一个凸包。）
参考做法：
#include <iostream>
#include <deque>
#include <vector>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
using std::cin; using std::cout;
using ll = long long;
constexpr int N = 1e6;
namespace m{ // }{{{
int in, ia, ib, ic;
int ix_[N+1];
ll dp_[N+1];
#define mkvis(arr) auto &arr(int pl){ return arr##_[pl+1]; }
mkvis(ix) mkvis(dp)
std::deque<int> todo;
ll calc(int x){ return ia*1ll*x*x+ib*1ll*x+ic; }
auto gety(int idx){ return ia*1ll*ix(idx)*ix(idx) + dp(idx); }
void work(){
cin >> in >> ia >> ib >> ic;
UP(i, 0, in){
cin >> ix(i);
ix(i) += ix(i-1);
}
//dp(-1) = 0;
todo.push_back(-1);
UP(i, 0, in){
while(todo.size() > 1){
int fr = *todo.begin(), frr = *++todo.begin();
if(gety(frr)-gety(fr) >= 1ll*(2*ia*ix(i)+ib)*(ix(frr)-ix(fr))){
todo.pop_front();
} else break;
}
{
int bx = todo.front(); // bestx
dp(i) = dp(bx) + calc(ix(i)-ix(bx));
}
while(todo.size() > 1){
int ed = *--todo.end(), edd = *----todo.end();
if((gety(ed)-gety(edd))*(ix(i)-ix(ed)) <
(gety(i)-gety(ed))*(ix(ed)-ix(edd))){
todo.pop_back();
} else break;
}
todo.push_back(i);
}
cout << dp(in-1);
}
} // {}}}
signed main(){std::ios::sync_with_stdio(0); cin.tie(0); m::work(); return 0;}