codeforce1519D Maximum Sum of Products（区间DP）

题目链接：codeforces 1519D

题目思路：

区间 dp /记忆化深搜，定义dp[i][j]为翻转区间 $[l,r]$ 的前后差值。状态转移方程为dp[l][r] = dfs(l+1, r-1) + a[r] * b[l] + a[l] * b[r] - a[l] * b[l] - a[r] * b[r]。

参考代码：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 5e3 + 10;
ll a[N], b[N], dp[N][N];
ll dfs(int l, int r) {
   
    if (l >= r) return 0;
    if (dp[l][r] != -1) return dp[l][r];
    dp[l][r] = dfs(l+1, r-1) + a[l] * b[r] + a[r] * b[l] - a[l] * b[l] - a[r] * b[r];
    return dp[l][r];
}
int main() {
   
    memset(dp, -1, sizeof(dp));
    int n;
    ll d = 0, sum = 0;
    cin >> n;
   	for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
   
        cin >> b[i];
        sum += a[i] * b[i];
    }
    for (int i = 1; i <= n; i++) {
   
        for (int j = 1; j <= n; j++) {
   
            d = max(d, dfs(i, j));
        }
    }
	cout << sum + d << endl;
    return 0;
}