CF1519 D.Maximum Sum of Products【区间DP】

题目链接：codeforces 1519D

题解

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}