Educational Codeforces Round 108 (D记忆化搜索)

题目大意：

给定两个长度为n(n<=5000)的整型数组a,b
可以对数组a进行至多一次以下操作：
选择l,r并对l到r进行翻转
求\(\sum\)a\(_i\)*b\(_i\)的最大值

解题思路：

因为n<=5000,所以我们考虑可以枚举操作区间l,r，因为对于一个大区间操作过后，对小区间再次进行操作所能获得的最大值是不变的，所以我们考虑这样一个dp，f[i][j]表示对区间[i,j]进行操作后该所能获得的最大值。
对于非操作区间，我们可以用前缀和优化计算，最后进行记忆化搜索即可。

代码实现：

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e5 + 10, inf = 1e18;

int n;

int f[5100][5100];
int a[N];
int b[N];
int pre[N];
int get(int l,int r){
	if(l == r) return a[l]*b[l];
	if(l>r) return 0;
	if(~f[l][r]) return f[l][r];
	return f[l][r] = a[l]*b[r]+a[r]*b[l]+get(l+1,r-1);
}
void solve() {
	cin>>n;
	memset(f,-1,sizeof f);
	for(int i = 1;i <= n;++i) cin>>a[i];
	for(int i = 1;i <= n;++i){
		cin>>b[i];
		pre[i] = pre[i-1]+a[i]*b[i];
	}
	int maxn = 0;
	for(int l = 1;l <= n;++l){
		for(int r = l;r<=n;++r){
			maxn = max(maxn,pre[l-1]+pre[n]-pre[r]+get(l,r));
		}
	}
	cout<<maxn<<endl;
	
}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
//	cin >> tt;
	while (tt--) solve();


	return 0;
}