您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

D. Maximum Sum of Products(dp)

最近在cf上刷math的题,这道题感觉挺好,1600的题。

题目链接

题目大意:给出n的长度的a,b两数组,你可以至多一次的反转a的子数组(连续),使得 ∑ i = 1 n a i ∗ b i \displaystyle\sum_{i=1}^{n} a_i*b_i i=1naibi最大化。

分析:n的范围是5000,可以开个二维dp,第一维表示反转的子数组的初始下标,第二维表示子数组的长度(也可以直接表示子数组的末尾下标,目前先按照我当时敲的代码来讲,两者的效果是一样的),dp的值表示子串反转后,在这个子串对应的区间内的ai * bi 的值。至于没有反转的区间,我们可以用前缀后缀预先处理出来,最终答案再加上。
现在就会有dp[i][len] = dp[i + 1][len - 2] + a[i] * b[i + len - 1] + b[i] * a[i + len - 1] 。可以这样理解:反转一个子串的操作可以分解为先反转中间len - 2的子串,再把第一个和最后一个交换。

code:

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define int long long
const int N = 5100;
const int INF = 0x3f3f3f3f;
int a[N], b[N];
int pre[N], hou[N];
int dp[N][N];

signed main(int argc, char const *argv[]) {
    int n;
    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++) {
        pre[i] = pre[i - 1] + a[i] * b[i];
    }
    for (int i = n; i >= 1; i--) {
        hou[i] = hou[i + 1] + a[i] * b[i];
    }
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        dp[i][1] = a[i] * b[i];
        ans = max(ans, pre[i - 1] + dp[i][1] + hou[i + 1]);

        dp[i][2] = a[i] * b[i + 1] + a[i + 1] * b[i];
        ans = max(ans, pre[i - 1] + dp[i][2] + hou[i + 2]);

        for (int len = 3; i + len - 1 <= n; len++) {
            dp[i][len] = dp[i + 1][len - 2];
            dp[i][len] += a[i] * b[i + len - 1] + b[i] * a[i + len - 1];
            ans = max(ans, pre[i - 1] + dp[i][len] + hou[i + len]);
        }
    }

    cout << ans << endl;
    return 0;
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进