本文主要是介绍Educational Codeforces Round 108 (Rated for Div. 2) D. Maximum Sum of Products，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
虽然说并没有系统学过区间DP，但这题的状态转移方程真的不难推，自己在打cf的时候过于在乎rating的变化而忽略了更为重要的东西，以此为戒。
令dp[i][j]为反转区间[i,j]所获得的价值。
dp[i][j] = dp[i+1][j-1] + a[l]*b[r] + a[r]*b[l] - a[l]*b[l] - a[r]*b[r];
可记忆化搜索可递推
#include<bits/stdc++.h>
using namespace std;#define de(x) cout << #x << " == " << x << endltypedef long long LL;
typedef pair<int, int> P;const int maxn = 5000 + 10;
const int M_MAX = 50000 + 10;
const int mod = 1e9;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6; int n;
LL a[maxn], b[maxn], dp[maxn][maxn];
LL sum;void solve() {cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) cin >> b[i];for(int i = 1; i <= n; i++) {sum += a[i] * b[i];}LL res = 0;for(int l = n - 1; l >= 1; l--) {for(int r = l + 1; r <= n; r++) {dp[l][r] = dp[l+1][r-1] + a[l]*b[r] + a[r]*b[l] - a[l]*b[l] - a[r]*b[r]; res = max(dp[l][r], res);}}cout << res + sum << endl;
}int main() {ios::sync_with_stdio(false);//srand(time(NULL)); //更新种子solve();return 0;
}
最后，期末考试加油！
这篇关于Educational Codeforces Round 108 (Rated for Div. 2) D. Maximum Sum of Products的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
