题目链接

题意

给你两个长度为n的数列a和b，要求你最多翻转一次a序列的一段连续的区间，使得$\displaystyle \sum_{i = 1} ^ n a_i*b_i$ 最大。

分析

首先暴力方法是先枚举区间长度再枚举起点，整个过程是 $O(n^2)$ 的，然后就是如何$O(1)$求出翻转后的值，先去找了一下每个翻转策略之间有没有冗余部分，发现没有啥可以优化的，想不出怎么快速求值，于是否掉了这个方法。开始思考DP，感觉是个区间DP，按照固有思维，将DP的属性设置为某个区间的最优解，但明显不对啊，因为只能翻转一次，只有一种情况，哪里来的最优解。然后就…卡题了。看了一眼题解，oh，wssb。就是区间DP，而且就是用一开始想的暴力找，O(1)算的思路，计算的过程用DP使得每次计算可以$O(1)$完成。

具体方法是：

定义 $dp[i][j]$ 为区间( i , j )翻转后与翻转前的 $\displaystyle \sum_{k = i} ^ j a_k*b_k$ 差值，于是 :

$dp[i][j] = dp[i+1][j-1] + a[i] * b[j] + a[j] * b[i] – a[i]*b[i] – a[j] * b[j]$

首先算出原数组的 $\displaystyle \sum_{i = 1} ^ n a_i*b_i$ ，然后记录所有翻转情况和原始数据的差值，然后再找到差值的最大值，两者相加就是答案。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
LL a[5555],b[5555];
LL dp[5555][5555];
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%lld",a+i);
    for(int i = 1; i <= n; i++) scanf("%lld",b+i);
    LL ans = 0, plus = 0;
    for(int i = 1; i <= n; i++) {
        ans += a[i] * b[i];
    }
    for(int len = 2; len <= n; len ++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = dp[i+1][j-1] + a[i] * b[j] + a[j] * b[i] - a[i]*b[i] - a[j] * b[j];
            plus = max(plus,dp[i][j]);
        }
    }
    cout << plus + ans <<endl;
    return 0;
}