『心静自然凉』大抵是因为情绪平和时副交感神经兴奋，体温略有降低导致的。吗？
其实是因为心脏停跳后血液循环终止、代谢中断，导致产热低于散热（？）
A - 征途
https://www.luogu.com.cn/problem/P4072
用完全平方公式展开得到 \(m^2\sigma^2=m\left(\sum {x_i}^2\right)-S^2\)，其中 \(S\) 为求和。
所以目标是最小化 \(\sum {x_i}^2\) 这个东西。令 \(f_{i,j}\) 表示第 \(i\) 天走到 \(j\)，得到：
\[ \begin{aligned} f_{i,j}&=\min\{f_{i-1,k}+(s_j-s_k)^2\}\\ &=\min\{f_{i-1,k}-2\times s_j\times s_k+{s_k}^2\}+{s_j}^2 \end{aligned} \]
最后得到的斜率式子是 \(\dfrac {f_{i - 1, a}-f_{i - 1, b}+{s_a}^2-{s_b}^2}{2(s_a-s_b)}<s_j\)，由于 \(s_j\) 单增，单调队列维护递减斜率即可 更正：是递增斜率。原因是 \(<\) 是弹出条件，而非保留条件……
#include <bits/stdc++.h>
const long long inf = 1e9;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
std::vector<long long> s(n + 1);
auto sum(0ll);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
s[i] = s[i - 1] + a[i];
sum += a[i];
}
std::vector<std::vector<long long> > f(m + 1, std::vector<long long> (n + 1, inf));
f[0][0] = 0ll;
for (int i = 1; i <= m; ++i) {
auto f1 = [&](int a, int b) {
return f[i - 1][a] - f[i - 1][b] + s[a] * s[a] - s[b] * s[b];
};
auto f2 = [&](int a, int b) {
return 2 * (s[a] - s[b]);
};
std::vector<int> q(n + 1);
int h = 0, t = -1;
q[++t] = i - 1;
for (int j = i; j <= n; ++j) {
for (; h < t && f1(q[h + 1], q[h]) < s[j] * f2(q[h + 1], q[h]); ++h);
f[i][j] = f[i - 1][q[h]] + (s[j] - s[q[h]]) * (s[j] - s[q[h]]);
for (; h < t && f1(j, q[t]) * f2(q[t], q[t - 1]) < f1(q[t], q[t - 1]) * f2(j, q[t]); --t);
q[++t] = j;
}
}
std::cout << m * f[m][n] - sum * sum << '\n';
return 0;
}B - 刷野 III
https://www.luogu.com.cn/problem/P10074
发现最坏情况就是每次『试探』都不中的情况，再试探中最坏的那一个。为啥呢，相当于我们每次攻击的一定是未知元素中血最多的一个。既然已经试探出了比阈值大的所有元素，那么下一个攻击的就一定是阈值本身，如果这次跳过它，它就会成为下一次试探失败的元素。这显然不如一开始就直接用新阈值试探。
从大到小排序。令 \(f_{j, i}\) 表示只确定了前 \(i\) 大的数，已经杀了 \(j\) 个人的最坏情况最小代价。那么显然这一次的阈值是 \(a_i\)。随便选出上一次的阈值 \(a_k\)，那么中间这一段待确定的元素数量为 \(i-k\)。那么有：
\[ \begin{aligned} f_{j, i}&=\min\limits_{k<i}\{f_{j-1,k}+(i-k)\times a_i\}\\ &=\min\limits_{k<i}\{f_{j-1,k}-k\times a_i\}+i\times a_i \end{aligned} \]
经过验证，虽然这个式子和题解长得不一样，但是是对的 因为我 n^3 暴力 A 了
推出斜优形式 \(\dfrac {f_{j-1,A}-f_{j-1,B}}{A-B}<a_i\)，但我的朋友，\(a_i\) 是递减的。所以用单调栈维护递增斜率即可。或者你也可以学习 grisses 打一个单调队列上二分
#include <bits/stdc++.h>
const long long inf = 1e12;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("P10074_4.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::sort(a.begin() + 1, a.end(), std::greater<long long> ());
std::vector<std::vector<long long> > f(m + 1, std::vector<long long> (n + 1, inf));
f[0][0] = 0ll;
for (int j = 1; j <= m; ++j) {
std::vector<int> q(n + 1);
int t = -1;
q[++t] = j - 1;
auto f1 = [&](int A, int B) {
return f[j - 1][A] - f[j - 1][B];
};
auto f2 =[&](int A, int B) {
return A - B;
};
for (int i = j; i <= n; ++i) {
for (; t >= 1 && f1(q[t], q[t - 1]) > a[i] * f2(q[t], q[t - 1]); --t);
f[j][i] = f[j - 1][q[t]] + (i - q[t]) * a[i];
for (; t >= 1 && f1(i, q[t]) * f2(q[t], q[t - 1]) < f1(q[t], q[t - 1]) * f2(i, q[t]); --t);
q[++t] = i;
}
}
auto res(inf);
for (int i = m; i <= n; ++i)
res = std::min(res, f[m][i]);
std::cout << res << '\n';
return 0;
}C - TRAKA
https://www.luogu.com.cn/problem/P7747
稍微手玩一下就可以发现，假如第 \(j\) 个人在第 \(i\) 次的工作时间为 \([L_{j,i},R_{j,i}]\)，第 \(i-1\) 次为 \([L_{j,i-1},R_{j,i-1}]\)，那么要求 \(L_{j,i}\ge R_{j,i-1}\)。
令 \(s_j\) 为 \(t\) 的前缀和。假设第 \(i-1\) 次加工于 \(x_{i-1}\) 开始，那么我们可以把上式转写为 \(x_{i}+s_{j-1}\times f_{i}\ge x_{i-1}+s_j\times f_{i-1}\)。也即 \(x_i-x_{i-1}\ge s_j\times f_{i-1}-s_{j-1}\times f_i\)。
显然需要找到一个 \(j\) 使得 RSH 取得最大值；现在就可以考虑斜率优化了。由于所有项都和 \(i\) 有关，想到两边同除 \(f_{i}\) 消掉一个 \(i\) 有关的系数，最后化出来的斜优形式是 \(\dfrac {s_A-s_B}{s_{A-1}-s_{B-1}}>\dfrac {f_{i-1}}{f_i}\)。由于 RSH 不单调，把所有 \(j\) 塞到队列里维护递减斜率，打二分即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<long long> a(n + 1), w(m + 1), s(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], s[i] = s[i - 1] + a[i];
for (int i = 1; i <= m; ++i)
std::cin >> w[i];
std::vector<long long> f(m + 1);
std::vector<int> q(n + 1);
int h = 0, t = -1;
q[++t] = 1;
for (int i = 2; i <= n; ++i) {
for (; h < t && (s[i] - s[q[t]]) * (s[q[t] - 1] - s[q[t - 1] - 1]) > (s[q[t]] - s[q[t - 1]]) * (s[i - 1] - s[q[t] - 1]); --t);
q[++t] = i;
}
for (int i = 2; i <= m; ++i) {
int to = q[h];
for (int l = h + 1, r = t, mid; l <= r; ) {
mid = (l + r) >> 1;
if ((s[q[mid]] - s[q[mid - 1]]) * w[i - 1] > w[i] * (s[q[mid] - 1] - s[q[mid - 1] - 1]))
to = q[mid], l = mid + 1;
else
r = mid - 1;
}
f[i] = f[i - 1] + s[to] * w[i - 1] - s[to - 1] * w[i];
}
std::cout << f[m] + w[m] * s[n] << '\n';
return 0;
}D - 柠檬
https://www.luogu.com.cn/problem/P5504
- 观察零：原问题『从两端取』可以转化为分段问题，故从其中一端考虑即可。
- 观察一：若有一段连续的 \(x\)，完整的比拆开的更优。
- 观察二：如果一段 \(x\) 中夹杂了一些其他元素，那么在哪里分段是说不准的。
- 观察三：如果选取的区间是 \([1,r]\)，那么贪心地想，\(a_r\) 一定是关键值，不然取 \(a_r\) 就浪费了。
- 观察四：如果选取的区间是 \([l,r]\)，那么由观察四，\(a_l=a_r\)，且该值为关键值。
结合这几个观察，令 \(c_i\) 表示 \(a_i\) 在 \([1,i]\) 中出现次数，\(f_i\) 表示这一段以 \(i\) 结尾的最大价值：
\[ \begin{aligned} f_i&=\max\limits_{j<i,a_{j+1}=a_i}\{f_j+a_i\times (c_i-c_{j + 1} + 1)^2\}\\ &=\max\limits_{j<i,a_{j+1}=a_i}\{f_j+a_{j+1}\times {c_{j+1}}^2-2\times c_i\times a_{j+1}\times c_{j+1}-2\times c_{j+1}\times a_{j+1}\}+a_i\times(c_i-1)^2 \end{aligned} \]
（怎么这么大一堆。）最后可以化出 \(\dfrac {f_A-f_B+a_{A+1}\cdot c_{A+1}\cdot (c_{A+1}-2)-a_{B+1}\cdot c_{B+1}\cdot (c_{B+1}-2)}{2(c_{A+1} - c_{B+1})}>c_i\times a_i\)。发现对于每一种 \(a_i\)，\(c_i\times a_i\) 是单增的。单调栈维护即可。
这其实提醒我们关于代换的问题——显然，当与 \(i\) 的项、与 \(j\) 有关的项之间存在代换关系时，应该尽量往 \(j\) 的方向靠。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("7.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<long long> a(n + 1), c(n + 1), la(10001);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
c[i] = c[la[a[i]]] + 1, la[a[i]] = i;
}
std::vector<long long> f(n + 1);
std::vector<int> _t(10001, -1);
std::vector<std::vector<int> > _q(10001);
auto f1 = [&](int A, int B) {
return f[A] - f[B] + a[A + 1] * c[A + 1] * (c[A + 1] - 2) - a[B + 1] * c[B + 1] * (c[B + 1] - 2);
};
auto f2 = [&](int A, int B) {
return 2 * (c[A + 1] - c[B + 1]);
};
++_t[a[1]], _q[a[1]].push_back(0);
for (int i = 1; i <= n; ++i) {
{
auto &t = _t[a[i]];
auto &q = _q[a[i]];
for (; t >= 1 && f1(q[t], q[t - 1]) < c[i] * a[i] * f2(q[t], q[t - 1]); --t);
f[i] = f[q[t]] + a[i] * (c[i] - c[q[t] + 1] + 1) * (c[i] - c[q[t] + 1] + 1);
}
if (i < n) {
auto &t = _t[a[i + 1]];
auto &q = _q[a[i + 1]];
for (; t >= 1 && f1(i, q[t]) * f2(q[t], q[t - 1]) > f1(q[t], q[t - 1]) * f2(i, q[t]); --t);
q.resize(++t + 1), q[t] = i;
}
}
std::cout << f[n] << '\n';
return 0;
}E - Knapsack with Diminishing Values
https://atcoder.jp/contests/abc373/tasks/abc373_f
发现和 单调队列优化多重背包 有异曲同工之妙。
不妨令 \(v_i\) 表示体积，\(w_i\) 表示价值。对于每一个 \(i\)，把所有体积按模 \(v_i\) 的余数分类，设为 \(j\cdot v_i+x\)。对于 \(k\cdot v_i+x\)，有：
\[ \begin{aligned} f_{i,j\cdot v_i+x}&=\max\limits_{k<j}\{f_{i-1,k\cdot v_i+x}+(j-k)\cdot w_i-(j-k)^2\}\\ &=\max\limits_{k<j}\{f_{i-1,k\cdot v_i+x}-k\cdot w_i-k^2+2\times j\times k\}-j^2+j\cdot w_i \end{aligned} \]
则得到 \(\dfrac {f_{i-1,A\cdot v_i+x}-f_{i-1,B\cdot v_i+x}+(B-A)\cdot w_i - A^2+B^2}{2(B-A)}<j\)。注意分母为负。总之单调队列维护递增斜率即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<long long> v(n + 1), w(n + 1);
std::vector<std::vector<long long> > f(n + 1, std::vector<long long> (m + 1));
for (int i = 1; i <= n; ++i) {
std::cin >> v[i] >> w[i];
for (int x = 0; x < v[i]; ++x) {
int h = 0, t = -1;
std::vector<int> q;
auto f1 = [&](int A, int B) {
return f[i - 1][A * v[i] + x] - f[i - 1][B * v[i] + x] + (B - A) * w[i] - A * A + B * B;
};
auto f2 = [&](int A, int B) {
return 2 * (B - A);
};
for (int j = 0, J = x; J <= m; ++j, J += v[i]) {
for (; h < t && f1(q[h + 1], q[h]) > j * f2(q[h + 1], q[h]); ++h);
f[i][J] = f[i - 1][J];
if (h <= t)
f[i][J] = std::max(f[i][J], f[i - 1][q[h] * v[i] + x] + (j - q[h]) * w[i] - (j - q[h]) * (j - q[h]));
for (; h < t && f1(j, q[t]) * f2(q[t], q[t - 1]) < f1(q[t], q[t - 1]) * f2(j, q[t]); --t);
q.resize(++t + 1), q[t] = j;
}
}
}
std::cout << f[n][m] << '\n';
return 0;
}F - Managing Telephone Poles
https://codeforces.com/problemset/problem/1575/M
？观察到性质然后被自己忽略了。非常值得批评。
不难写出类似斜率优化的式子 \(S(i,j)=\min\{ {x_k}^2-2\times i\times x_k+{y_k}^2-2\times j \times y_k\}+i^2+j^2\)。
会下意识尝试固定 \(i\)，就可以 \(O(n^2m)\) 完成任务，似乎不太行。顺着这个想法会观察到，固定 \(i\) 之后，每一列的 poles 中只有和第 \(i\) 行最近的才会有贡献。
这个是好做的，且这样的相邻点数量是 \(O(m)\) 的；于是将 \(i\) 视为常数进行变形，若将所有 poles 按 \(y\) 从小到大排序就能得到斜率形式 \(\dfrac { {x_A}^2-{x_B}^2+{y_A}^2-{y_B}^2-2\times i\times(x_A-x_B)}{2(y_A-y_B)}<j\)。维护递增斜率就能 \(O(n^2)\) 完成问题。
那么找相邻点这一步大可以摆烂写二分。所以总共是 \(O(nm\log m)\) 的。
不要像我一样把两边最近的都加进队列，不然你会有分母为 \(0\) 的斜率 
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m, ++n, ++m;
std::vector<std::vector<int> > tag(n + 1, std::vector<int> (m + 1));
std::vector<std::vector<int> > g(m + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
char t;
std::cin >> t;
if (t == '1')
g[j].push_back(i), tag[i][j] = 1;
}
struct node { long long x, y; };
auto res(0ll);
for (int i = 1; i <= n; ++i) {
std::vector<node> p;
for (int j = 1; j <= m; ++j) {
int to = std::lower_bound(g[j].begin(), g[j].end(), i) - g[j].begin();
if (to < (int)g[j].size()) {
p.push_back({ g[j][to], j });
if (g[j][to] != i && to != 0 && g[j][to] - i > i - g[j][to - 1])
p.back() = { g[j][to - 1], j };
}
else if (to != 0)
p.push_back({ g[j][to - 1], j });
}
std::vector<int> q(m + 1);
int h = 0, t = -1;
auto f1 = [&](node A, node B) {
return A.x * A.x - B.x * B.x + A.y * A.y - B.y * B.y - 2 * i * (A.x - B.x);
};
auto f2 = [&](node A, node B) {
return 2 * (A.y - B.y);
};
for (int j = 0; j < (int)p.size(); ++j) {
for (; h < t && f1(p[j], p[q[t]]) * f2(p[q[t]], p[q[t - 1]]) < f1(p[q[t]], p[q[t - 1]]) * f2(p[j], p[q[t]]); --t);
q[++t] = j;
}
for (int j = 1; j <= m; ++j) {
for (; h < t && f1(p[q[h + 1]], p[q[h]]) < j * f2(p[q[h + 1]], p[q[h]]); ++h);
res += (p[q[h]].x - i) * (p[q[h]].x - i) + (p[q[h]].y - j) * (p[q[h]].y - j);
}
}
std::cout << res << '\n';
return 0;
}G - Partition Game
https://codeforces.com/problemset/problem/1527/E
发现不太斜优，终于给我浸泡了两天斜优内容的大脑加了勺新的底物。
令 \(f_{i,j}\) 表示第 \(i\) 段以 \(j\) 结尾的最小代价；对 \(w\) 套用四边形不等式变式 \(w(l-1,r+1)+w(l,r)\ge w(l-1,r)+w(l,r+1)\) 发现成立（其中大多数时候能取等；部分特殊情况取到大于号）。
那么发现可以用分治优化。发现 \(w\) 不那么能快速求；还是套用 Yet Another Minimization Problem 中的方法，用类似莫队的方式求解。
发现这个莫队套路也很熟悉了，直接用双端队列维护即可。复杂度 \(O(nk\log n)\)，看着不太安全。但注意到我们在 20 个月前的提交中使用了 \(O(nk\log n)\) 的线段树，所以能过的兄弟。
鉴于 deque 的时空常数都大得吓人，所以我用静态 vector 模拟 deque 了。
跑得比我之前线段树的一半还快，兄弟。
#include <bits/stdc++.h>
const int inf = 1e18;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > pos(n + 1);
std::vector<int> a(n + 1), _h(n + 1), _t(n + 1, -1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], pos[a[i]].push_back(i);
std::vector<std::vector<long long> > f(m + 1, std::vector<long long> (n + 1, inf));
f[0][0] = 0ll;
auto w = [&](int ql, int qr) {
static int l = 1, r = 0;
static auto res(0ll);
for (; l > ql; ) {
--l;
auto &h = _h[a[l]], &t = _t[a[l]];
auto &q = pos[a[l]];
if (h <= t)
res -= q[t] - q[h];
res += q[t] - q[--h];
}
for (; r > qr; ) {
auto &h = _h[a[r]], &t = _t[a[r]];
auto &q = pos[a[r]];
res -= q[t--] - q[h];
if (h <= t)
res += q[t] - q[h];
--r;
}
for (; r < qr; ) {
++r;
auto &h = _h[a[r]], &t = _t[a[r]];
auto &q = pos[a[r]];
if (h <= t)
res -= q[t] - q[h];
res += q[++t] - q[h];
}
for (; l < ql; ) {
auto &h = _h[a[l]], &t = _t[a[l]];
auto &q = pos[a[l]];
res -= q[t] - q[h++];
if (h <= t)
res += q[t] - q[h];
++l;
}
return res;
};
for (int t = 1; t <= m; ++t) {
std::function<void(int, int, int, int)> calc = [&](int l, int r, int lp, int rp) {
if (l > r)
return;
if (l == r) {
for (int i = lp; i <= rp && i < l; ++i)
f[t][l] = std::min(f[t][l], f[t - 1][i] + w(i + 1, l));
return;
}
int mid = (l + r) >> 1, p = -1;
for (int i = lp; i <= rp && i < mid; ++i)
if (f[t - 1][i] + w(i + 1, mid) < f[t][mid])
f[t][mid] = f[t - 1][i] + w(i + 1, mid), p = i;
calc(l, mid - 1, lp, p), calc(mid + 1, r, p, rp);
return;
};
calc(t, n, t - 1, n - 1);
}
std::cout << f[m][n] << '\n';
return 0;
}H - Battle Lemmings
https://codeforces.com/problemset/problem/1420/E
容易发现 \(0\) 的数目不变，答案就是 \(0\) 的对数 - 连续 \(0\) 的对数。
然后有一个我们很熟悉的 trick，随便找一个目标序列，那么花费的操作次数就是每个对应的 \(1\) 的位置差。令 \(f_{i,j,k}\) 表示用了 \(i\) 次操作、\(j\) 个 \(1\)、最后一个 \(1\) 在 \(k\) 的最小连续 \(0\) 对数。那么有：
\[ \begin{aligned} f_{i,j,k}&=\min\limits_{p<k}\left\{f_{i-|k-pos_j|,j-1,p}+\dfrac {(k-p-1)(k-p-2)}2\right\}\\ &=\min\left\{f_{i-|k-pos_j|,j-1,p}-k\cdot p+\dfrac {p(p + 2)}2\right\}+\dfrac {k^2-3k+2}2 \end{aligned} \]
发现这个式子是 \(O(n^5)\) 的，而且看起来很斜优，化为斜率形式 \(\dfrac{2\times f_A-2\times f_B+A(A+2)-B(B+2)}{2(A-B)}<k\)。维护递增斜率就可以 \(O(n^4)\) 做了。
Tip：当时写着写着愣住了，比如这个 \(i-|k-pos_j|\) 不是一直在动吗。解决方案？同时维护很多个队列即可。
注意还要把最后一个 \(1\) 之后连续 \(0\) 的代价算上。
#include <bits/stdc++.h>
const long long inf = 1e9;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1);
std::vector<long long> pos(1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
if (a[i] == 1)
pos.push_back(i);
}
int m = n * (n - 1) / 2;
std::vector<std::vector<std::vector<long long> > > f(pos.size(), std::vector<std::vector<long long> > (m + 1, std::vector<long long> (n + 1, inf)));
f[0][0][0] = 0ll;
for (int j = 1; j < (int)pos.size(); ++j) {
std::vector<std::vector<int> > _q(m + 1, std::vector<int> (n + 1));
std::vector<int> _h(m + 1), _t(m + 1, -1);
for (int k = 0; k <= n; ++k)
for (int i = m; i >= 0; --i) {
if (i >= std::abs(k - pos[j])) {
auto f1 = [&](long long A, long long B) {
return 2 * f[j - 1][i - std::abs(k - pos[j])][A] - 2 * f[j - 1][i - std::abs(k - pos[j])][B] + A * (A + 2) - B * (B + 2);
};
auto f2 = [&](long long A, long long B) {
return 2 * (A - B);
};
auto &h = _h[i - std::abs(k - pos[j])], &t = _t[i - std::abs(k - pos[j])];
auto &q = _q[i - std::abs(k - pos[j])];
for (; h < t && f1(q[h + 1], q[h]) < k * f2(q[h + 1], q[h]); ++h) {}
if (h <= t)
f[j][i][k] = std::min(inf, f[j - 1][i - std::abs(k - pos[j])][q[h]] + (k - q[h] - 1) * (k - q[h] - 2) / 2);
}
auto f1 = [&](long long A, long long B) {
return 2 * f[j - 1][i][A] - 2 * f[j - 1][i][B] + A * (A + 2) - B * (B + 2);
};
auto f2 = [&](long long A, long long B) {
return 2 * (A - B);
};
auto &h = _h[i], &t = _t[i];
auto &q = _q[i];
for (; h < t && f1(k, q[t]) * f2(q[t], q[t - 1]) < f1(q[t], q[t - 1]) * f2(k, q[t]); --t);
q[++t] = k;
}
}
auto res(-inf);
int cnt = n - (int)pos.size() + 1;
cnt = cnt * (cnt - 1) / 2;
for (int i = 0; i <= m; ++i) {
for (int k = 0; k <= n; ++k)
res = std::max(res, cnt - f.back()[i][k] - (n - k) * (n - k - 1) / 2);
std::cout << res << ' ';
}
std::cout << '\n';
return 0;
}A - Yakiniku Restaurants
https://atcoder.jp/contests/arc067/tasks/arc067_d
发现固定左右端点后，收益是可以贪心算的；下意识想到只固定左端点，那么右端点应该就可以用单调队列之类的搞一搞。
先提前把所有东西塞到队列里。左端点一开始在最右边；往左边动一下之后，就可以更新每种菜的队列；发现在所有元素中作决策点的不总是队头；这个地方用 单调递减的单调栈 是极好的。这里的单调栈其实就类似 四边形不等式中的单调数据结构 了。
维护单调栈中每个决策点的影响区间；显然每个右端点的答案变化量相同；用个类似于差分的东西记录一下就好了。
复杂度 \(O(n^2)\)。
#include <bits/stdc++.h>
const long long inf = 1e18;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<long long> s(n + 1), f(n + 1);
for (int i = 2; i <= n; ++i) {
std::cin >> s[i], s[i] += s[i - 1];
f[i] = -s[i];
}
std::vector<std::vector<int> > a(n + 1, std::vector<int> (m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
std::cin >> a[i][j];
struct node { int j, l, r; };
std::vector<std::stack<node> > _q(m + 1);
auto res(-inf);
for (int l = n; l; --l) {
std::vector<long long> d(n + 1);
auto add = [&](int l, int r, long long v) {
d[l] += v;
if (r != n)
d[r + 1] -= v;
return;
};
for (int j = 1; j <= m; ++j) {
auto &q = _q[j];
node now = { j, l, l };
add(l, l, a[l][j]);
for (; !q.empty() && a[l][j] >= a[q.top().l][q.top().j]; q.pop()) {
now.r = q.top().r;
add(q.top().l, q.top().r, a[l][j] - a[q.top().l][q.top().j]);
}
q.push(now);
}
std::partial_sum(d.begin() + 1, d.end(), d.begin() + 1);
for (int r = l; r <= n; ++r) {
f[r] += d[r];
res = std::max(res, f[r] + s[l]);
}
}
std::cout << res << '\n';
return 0;
}B - Jellyfish and Miku
https://codeforces.com/problemset/problem/1874/D
唉数列。唉概统。在数学讲义上折磨了我一遍之后还要到这儿来折磨我。
假设已经知道了 \(a\)，考虑求期望步数。设 \(E_i\) 为从 \(i\) 出发走到 \(n\) 的期望步数。那么有：
\[ E_i=\begin{cases} E_1+1&i=0\\ 0&i=n\\ E_i=(E_{i-1}+1)\cdot \dfrac {a_i}{a_{i+1}+a_i}+(E_{i+1}+1)\cdot \dfrac {a_{i+1}}{a_{i+1}+a_{i}}&\text{otherwise} \end{cases} \]
（提示：从『\(i\) 下一步会走哪个方向』考虑。）
接下来就可以利用你的高中数学知识进行一个 \(f_0\) 的求，（一堆过程），得到 \(E_0=n+2\times \sum\limits_{i=1}^n\dfrac {\sum_{j\le i}a_j}{a_i}\)，然后想要最小化这个东西。
不妨令 \(f_{i,j}\) 表示到 \(i\) 时已经分配走了 \(j\) 体积，\(\sum_{k=1}^i \dfrac {\sum_{l\le k}a_l}{a_k}\) 的最小值，有 \(f_{i,j}=\min\limits_{k<j}\left\{f_{i-1,k}+\dfrac {k}{j - k}\right\}\)。发现它大抵是满足四边形不等式的，按照 2D/1D DP 优化的结论，代入 \(p_{i,j-1}<p_{i,j}<p_{i+1,j}\) 可以 \(O(nm)\) 解决问题。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > p(n + 1, std::vector<int> (m + 1));
std::vector<std::vector<long double> > f(n + 1, std::vector<long double> (m + 1, 1e18));
f[0][0] = 0ll;
for (int j = 1; j <= m; ++j)
for (int i = std::min(j, n); i; --i) {
int to = ((i == std::min(j, n)) ? j : std::min(p[i + 1][j], j));
for (int k = p[i][j - 1]; k <= to; ++k)
if (f[i - 1][k] + k * 1. / (j - k) < f[i][j])
f[i][j] = f[i - 1][k] + k * 1. / (j - k), p[i][j] = k;
// printf("f[%d][%d] = %Lf, p = %d\n", i, j, f[i][j], p[i][j]);
}
std::cout << std::fixed << std::setprecision(10) << n + 2 * f[n][m] << '\n';
return 0;
}Cut the Sequence
https://www.luogu.com.cn/problem/P10977
通知：区间最值 不满足 四边形不等式。
其实在猜的时候是举了反例的，但是大脑萎缩了推着推着忘记符号了 😅
看到 \(f_i=\min\limits_{g(i)\le j<i}\{f_j+\max\{a_{j+1\sim i}\}\}\) 这个 \(j\) 的范围其实是有点单调队列优化的感觉的，但这个最大值传统的单调队列不是很可做。可以注意到最大值这一项有点 单调队列 后缀最大值的感觉（实际上就是）；一个很自然的想法是利用这个最大值影响的区间，维护 \(f\) 的线段树来暴力做。
另一个比较牛的做法是发现同一个下标的 \(f\) 和 \(a\) 的关系。首先需要注意到 \(f\) 单调不降；对于同一个 \(a\)，能取到的 \(f\) 就是最靠前的；维护一个 \(a\) 的单减队列，那么共用同一个 \(a\) 的就是相邻两个下标之间的部分，其最优决策在能取到的最前端取得；需要注意到队列里的贡献并不单调，需要用一个 multiset 来存储所有贡献并查找、更新。
需要注意单调队列里某个元素 \(f_{q_i}\) 结合的其实是 \(a_{q_{i+1}}\)。还需要注意队头的维护，可能需要一些小巧思。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("1.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
std::vector<long long> s(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], s[i] = s[i - 1] + a[i];
int h = 0, t = -1;
std::multiset<long long> st;
std::vector<long long> f(n + 1);
std::vector<std::pair<int, int> > q(n + 1);
q[++t] = { 0, 0 }, a[0] = 0x3f3f3f3f;
for (int i = 1; i <= n; ++i) {
for (; s[i] - s[q[h].second] > m; ) {
st.erase(st.find(f[q[h].second] + a[q[h + 1].first]));
if (++q[h].second >= q[h + 1].first)
a[q[++h].first] = 0x3f3f3f3f;
else
st.insert(f[q[h].second] + a[q[h + 1].first]);
}
for (; h < t && a[q[t].first] <= a[i]; --t)
st.erase(st.find(f[q[t - 1].second] + a[q[t].first]));
st.insert(f[q[t].second] + a[i]), q[++t] = { i, i };
f[i] = *st.begin();
}
std::cout << f[n] << '\n';
return 0;
}