『心静自然凉』大抵是因为情绪平和时副交感神经兴奋，体温略有降低导致的。吗？
其实是因为心脏停跳后血液循环终止、代谢中断，导致产热低于散热（？）
#A - 征途
https://www.luogu.com.cn/problem/P4072
用完全平方公式展开得到 m2σ2=m(∑xi2)−S2，其中 S 为求和。
所以目标是最小化 ∑xi2 这个东西。令 fi,j 表示第 i 天走到 j，得到：
fi,j=min{fi−1,k+(sj−sk)2}=min{fi−1,k−2×sj×sk+sk2}+sj2
最后得到的斜率式子是 fi−1,a−fi−1,b+sa2−sb22(sa−sb)<sj，由于 sj 单增，单调队列维护递减斜率即可 更正：是递增斜率。原因是 < 是弹出条件，而非保留条件……
#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
发现最坏情况就是每次『试探』都不中的情况，再试探中最坏的那一个。为啥呢，相当于我们每次攻击的一定是未知元素中血最多的一个。既然已经试探出了比阈值大的所有元素，那么下一个攻击的就一定是阈值本身，如果这次跳过它，它就会成为下一次试探失败的元素。这显然不如一开始就直接用新阈值试探。
从大到小排序。令 fj,i 表示只确定了前 i 大的数，已经杀了 j 个人的最坏情况最小代价。那么显然这一次的阈值是 ai。随便选出上一次的阈值 ak，那么中间这一段待确定的元素数量为 i−k。那么有：
fj,i=mink<i{fj−1,k+(i−k)×ai}=mink<i{fj−1,k−k×ai}+i×ai
经过验证，虽然这个式子和题解长得不一样，但是是对的 因为我 n^3 暴力 A 了
推出斜优形式 fj−1,A−fj−1,BA−B<ai，但我的朋友，ai 是递减的。所以用单调栈维护递增斜率即可。或者你也可以学习 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 次的工作时间为 [Lj,i,Rj,i]，第 i−1 次为 [Lj,i−1,Rj,i−1]，那么要求 Lj,i≥Rj,i−1。
令 sj 为 t 的前缀和。假设第 i−1 次加工于 xi−1 开始，那么我们可以把上式转写为 xi+sj−1×fi≥xi−1+sj×fi−1。也即 xi−xi−1≥sj×fi−1−sj−1×fi。
显然需要找到一个 j 使得 RSH 取得最大值；现在就可以考虑斜率优化了。由于所有项都和 i 有关，想到两边同除 fi 消掉一个 i 有关的系数，最后化出来的斜优形式是 sA−sBsA−1−sB−1>fi−1fi。由于 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]，那么贪心地想，ar 一定是关键值，不然取 ar 就浪费了。
- 观察四：如果选取的区间是 [l,r]，那么由观察四，al=ar，且该值为关键值。
结合这几个观察，令 ci 表示 ai 在 [1,i] 中出现次数，fi 表示这一段以 i 结尾的最大价值：
fi=maxj<i,aj+1=ai{fj+ai×(ci−cj+1+1)2}=maxj<i,aj+1=ai{fj+aj+1×cj+12−2×ci×aj+1×cj+1−2×cj+1×aj+1}+ai×(ci−1)2
（怎么这么大一堆。）最后可以化出 fA−fB+aA+1⋅cA+1⋅(cA+1−2)−aB+1⋅cB+1⋅(cB+1−2)2(cA+1−cB+1)>ci×ai。发现对于每一种 ai，ci×ai 是单增的。单调栈维护即可。
这其实提醒我们关于代换的问题——显然，当与 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
发现和 单调队列优化多重背包 有异曲同工之妙。
不妨令 vi 表示体积，wi 表示价值。对于每一个 i，把所有体积按模 vi 的余数分类，设为 j⋅vi+x。对于 k⋅vi+x，有：
fi,j⋅vi+x=maxk<j{fi−1,k⋅vi+x+(j−k)⋅wi−(j−k)2}=maxk<j{fi−1,k⋅vi+x−k⋅wi−k2+2×j×k}−j2+j⋅wi
则得到 fi−1,A⋅vi+x−fi−1,B⋅vi+x+(B−A)⋅wi−A2+B22(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{xk2−2×i×xk+yk2−2×j×yk}+i2+j2。
会下意识尝试固定 i，就可以 O(n2m) 完成任务，似乎不太行。顺着这个想法会观察到，固定 i 之后，每一列的 poles 中只有和第 i 行最近的才会有贡献。
这个是好做的，且这样的相邻点数量是 O(m) 的；于是将 i 视为常数进行变形，若将所有 poles 按 y 从小到大排序就能得到斜率形式 xA2−xB2+yA2−yB2−2×i×(xA−xB)2(yA−yB)<j。维护递增斜率就能 O(n2) 完成问题。
那么找相邻点这一步大可以摆烂写二分。所以总共是 O(nmlogm) 的。
不要像我一样把两边最近的都加进队列，不然你会有分母为 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
发现不太斜优，终于给我浸泡了两天斜优内容的大脑加了勺新的底物。
令 fi,j 表示第 i 段以 j 结尾的最小代价；对 w 套用四边形不等式变式 w(l−1,r+1)+w(l,r)≥w(l−1,r)+w(l,r+1) 发现成立（其中大多数时候能取等；部分特殊情况取到大于号）。
那么发现可以用分治优化。发现 w 不那么能快速求；还是套用 Yet Another Minimization Problem 中的方法，用类似莫队的方式求解。
发现这个莫队套路也很熟悉了，直接用双端队列维护即可。复杂度 O(nklogn)，看着不太安全。但注意到我们在 20 个月前的提交中使用了 O(nklogn) 的线段树，所以能过的兄弟。
鉴于 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 的位置差。令 fi,j,k 表示用了 i 次操作、j 个 1、最后一个 1 在 k 的最小连续 0 对数。那么有：
fi,j,k=minp<k{fi−|k−posj|,j−1,p+(k−p−1)(k−p−2)2}=min{fi−|k−posj|,j−1,p−k⋅p+p(p+2)2}+k2−3k+22
发现这个式子是 O(n5) 的，而且看起来很斜优，化为斜率形式 2×fA−2×fB+A(A+2)−B(B+2)2(A−B)<k。维护递增斜率就可以 O(n4) 做了。
Tip：当时写着写着愣住了，比如这个 i−|k−posj| 不是一直在动吗。解决方案？同时维护很多个队列即可。
注意还要把最后一个 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(n2)。
#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，考虑求期望步数。设 Ei 为从 i 出发走到 n 的期望步数。那么有：
Ei={E1+1i=00i=nEi=(Ei−1+1)⋅aiai+1+ai+(Ei+1+1)⋅ai+1ai+1+aiotherwise
（提示：从『i 下一步会走哪个方向』考虑。）
接下来就可以利用你的高中数学知识进行一个 f0 的求，（一堆过程），得到 E0=n+2×n∑i=1∑j≤iajai，然后想要最小化这个东西。
不妨令 fi,j 表示到 i 时已经分配走了 j 体积，∑ik=1∑l≤kalak 的最小值，有 fi,j=mink<j{fi−1,k+kj−k}。发现它大抵是满足四边形不等式的，按照 2D/1D DP 优化的结论，代入 pi,j−1<pi,j<pi+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
通知：区间最值 不满足 四边形不等式。
其实在猜的时候是举了反例的，但是大脑萎缩了推着推着忘记符号了 😅
看到 fi=ming(i)≤j<i{fj+max{aj+1∼i}} 这个 j 的范围其实是有点单调队列优化的感觉的，但这个最大值传统的单调队列不是很可做。可以注意到最大值这一项有点 单调队列 后缀最大值的感觉（实际上就是）；一个很自然的想法是利用这个最大值影响的区间，维护 f 的线段树来暴力做。
另一个比较牛的做法是发现同一个下标的 f 和 a 的关系。首先需要注意到 f 单调不降；对于同一个 a，能取到的 f 就是最靠前的；维护一个 a 的单减队列，那么共用同一个 a 的就是相邻两个下标之间的部分，其最优决策在能取到的最前端取得；需要注意到队列里的贡献并不单调，需要用一个 multiset 来存储所有贡献并查找、更新。
需要注意单调队列里某个元素 fqi 结合的其实是 aqi+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;
}