杂项

枚举翻转中心后向左右扩展可以快速计算翻转每个区间后的答案。

时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[5001],b[5001];
long long sum[5001];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    transform(a+1,a+n+1,b+1,sum+1,[](int x,int y){return 1ll*x*y;});
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    long long ans=sum[n];
    for(int i=2;i<=n-1;i++){
        long long now=1ll*a[i]*b[i];
        int l=i-1,r=i+1;
        while(l>=1&&r<=n){
            now+=1ll*a[l]*b[r]+1ll*b[l]*a[r];
            ans=max(ans,sum[n]-sum[r]+sum[l-1]+now);
            l--,r++;
        }
    }
    for(int i=1;i<=n-1;i++){
        long long now=0ll;
        int l=i,r=i+1;
        while(l>=1&&r<=n){
            now+=1ll*a[l]*b[r]+1ll*b[l]*a[r];
            ans=max(ans,sum[n]-sum[r]+sum[l-1]+now);
            l--,r++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}