题解：CF1519D Maximum Sum of Products

· · 题解

CF1519D 题目传送门

题目大意

给定两个长度为 n 的整数数组 a 和 b。您可以翻转数组 a 中的至多一个子数组，而且是连续的子段。你的任务是翻转这样一个子数组，使得 \sum\limits_{i = 1}^{n} a_i \cdot b_i 的值最大。

解决思路

这道题用暴力一次一次算，然后比较，求出最大的乘积和输出就好。通过以每个位置 i 为中心，尝试交换其左右两侧的元素对，重新计算总和，并与当前最大总和 ans 进行比较，不断更新 ans，最终得到最大的总和。还有一些解释在代码注释中详情请看代码注释。

代码展示

#include <iostream>
#define ll long long
//不开long long见祖宗
using namespace std;

const int N = 5010;
int n;
ll sum, a[N], b[N];
//sum表示a,b对应元素mul之和(mul表示乘积)

int main()
{
    scanf("%d", &n);//建议scanf,更快
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]); 
        sum += a[i] * b[i];
        //计算初始sum 
    } 
    ll ans = sum;
    for(int i = 1; i <= n; i++)
    {//尝试以每个位置i为中心,调整左右两侧的元素对,以获取更大的总和
        ll sm1 = sum;
        for(int j = i - 1, k = i + 1; j >= 1 && k <= n; j--, k++)
        {//长度为奇数
            sm1 -= a[j] * b[j] + a[k] * b[k];
            sm1 += a[j] * b[k] + a[k] * b[j];
            //减去当前的mul，加上交换后的mul
            ans = max(ans, sm1);//为保证mul之和最大，每次取操作前后更大的值
        }
        sm1 = sum;
        for(int j = i, k = i + 1; j >= 1 && k <= n; j--, k++)
        {//长度为偶数
            sm1 -= a[j] * b[j] + a[k] * b[k];
            sm1 += a[j] * b[k] + a[k] * b[j];
            ans = max(ans, sm1);//方法一样
        }
    }
    printf("%d\n", ans);//建议printf,更快
    return 0;//换行是个好习惯
}