题面
有两个长为
n
n
n 的序列
a
a
a 和
b
b
b，至多反转
a
a
a 的一个子区间，最大化
∑
i
=
1
n
a
i
⋅
b
i
\sum_{i=1}^na_i\cdot b_i
∑i=1nai⋅bi 并输出这个值。
1
≤
n
≤
5000
1\leq n\leq5000
1≤n≤5000，答案不会爆 long long。
题解
绝大部分人都在考场上用的是官方题解的做法，基本没有什么别的做法了，如果有，那估计就是提交榜单最末尾那些
1900+ ms的做法吧。
数据非常小，再加上又是Div2，让人不禁想起暴力做法。朴素的暴力是枚举要翻转的区间
[
l
,
r
]
[l,r]
[l,r] ，然后把它带给答案的变化量加上，取最优输出。
这样是
O
(
n
3
)
O(n^3)
O(n3) 的，过不了。为什么这个暴力不可行，因为我们每次计算区间
[
l
,
r
]
[l,r]
[l,r] ，都要把整个
[
l
,
r
]
[l,r]
[l,r] 模拟翻转一遍在计算答案，这是低效的。
只要我们注意到
[
l
,
r
]
[l,r]
[l,r] 的答案可以从
[
l
+
1
,
r
−
1
]
[l+1,r-1]
[l+1,r−1] 的答案
O
(
1
)
O(1)
O(1) 转移过来，我们就解决这个问题了。这很好理解，因为这两个区间的旋转中心相等，它们的模拟翻转过程只有最边上不同。
你可以暴力从每个旋转中心往外扩展计算，也可以用 Dynamic Programming 仿照上面说的转移写。都是
O
(
n
2
)
O(n^2)
O(n2) 的，差别不大。
CODE
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 5005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
LL a[MAXN],b[MAXN];
int main() {
n = read();
LL sum = 0;
for(int i = 1;i <= n;i ++) a[i] = read();
for(int i = 1;i <= n;i ++) {
b[i] = read(); sum += a[i] * b[i];
}
LL ans = sum;
for(int i = 1;i <= n;i ++) {// 从中心扩展
LL sm = sum;
for(int j = i-1,k = i+1;j > 0 && k <= n;j --,k ++) { // 长度为奇数，中心是个点
sm -= a[j]*b[j] + a[k]*b[k];
sm += a[j]*b[k] + a[k]*b[j];
ans = max(ans,sm);
}
sm = sum;
for(int j = i,k = i+1;j > 0 && k <= n;j --,k ++) { // 长度为偶数，中心是个分界线
sm -= a[j]*b[j] + a[k]*b[k];
sm += a[j]*b[k] + a[k]*b[j];
ans = max(ans,sm);
}
}
printf("%lld\n",ans);
return 0;
}
