题目链接
题意
给你两个长度为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 ，然后记录所有翻转情况和原始数据的差值，然后再找到差值的最大值，两者相加就是答案。
代码
代码语言：javascript复制#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;
}
