https://codeforces.com/contest/1016/problem/C
题目大意
给出一个 $2 \times n$ 的矩阵，矩阵上每个位置有一个数字，代表每秒会多出 $a_{i, j}$ 的价值。第 $0s$ 从左上角出发，每次到达一个格子的时刻取到当前的价值，每一秒要强制走到某一个相邻的格子（四联通），问不重复的走完所有格子所能取到的最好代价是多少。
$1 \le n \le 3 \times 10^5$。$1 \le a_{i, j} \le 10^6$。
简要题解
观察：
想从左上角出发走完所有格子只有如下一种模式：
v > v > > > > v
> ^ > ^ < < < <
所以我们只要去枚举从上下反复，到左右走到头的变化的位置即可。
我们注意到贡献的形式是 $val_0 * 0 + val_1 * 1 + val * 2$ 的形式。对于左侧上下跳的部分我们可以直接模拟，而注意到右侧是横向的连续一段，对于这样的贡献，我们可以预处理两个前缀和 $\sum val_i$ 和 $\sum val_i * i$。然后对于对应的段，我们用 $\sum val_i$ 的倍数把值调整到我们想要的值即可。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<vector<LL>> a(2, vector<LL>(n));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
vector<vector<LL>> sum(2, vector<LL>(n));
vector<vector<LL>> sumil(2, vector<LL>(n));
vector<vector<LL>> sumir(2, vector<LL>(n));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
sum[i][j] = a[i][j] + (j ? sum[i][j - 1] : 0);
sumil[i][j] = a[i][j] * j + (j ? sumil[i][j - 1] : 0);
}
}
for (int i = 0; i < 2; i++) {
sumir[i][n - 1] = a[i][n - 1] * n + sumil[i ^ 1][n - 1];
for (int j = n - 2; j >= 0; j--) {
sumir[i][j] = a[i][j] * (n + n - 1 - j) + sumir[i][j + 1];
}
}
auto getsum = [&](int i, int l, int cnt) -> LL {
LL ans = sum[0][n - 1] + sum[1][n - 1];
if (l) ans -= sum[0][l - 1] + sum[1][l - 1];
LL diff = cnt - l;
ans *= diff;
ans += sumir[i ^ 1][l];
if (l) ans -= sumil[i][l - 1];
return ans;
};
LL ans = 0;
LL cur = 0;
LL cnt = 0;
for (int j = 0; j < n; j++) {
if (j & 1) {
cmax(ans, cur + getsum(1, j, cnt));
cur += a[1][j] * cnt;
cnt++;
cur += a[0][j] * cnt;
cnt++;
} else {
cmax(ans, cur + getsum(0, j, cnt));
cur += a[0][j] * cnt;
cnt++;
cur += a[1][j] * cnt;
cnt++;
}
// cerr << j << ' ' << cnt << ' ' << cur << ' ' << ans << endl;
}
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Mycraft Sand Sort - Codeforces Round 1005 (Div. 2)