题意

一个长度为n的非负整数序列,要求分割成k+1段,每次分割获得的价值是:分割后两端和的乘积。求获得的最大价值

$1 \leq n \leq 1e5, 1 \leq k \leq 200$

分析

最终答案和分割的次序是没有关系的。

证明可以考虑分割结束后重新合并的过程,发现合并的次序并没有影响,因此分割时的次序也不影响答案。

因为 $k$ 只有 $200$,所以很容易想到一个 $O(nk)$ 的 $dp$。

$dp[k][i]$ 表示第 $k$ 次分割前 $n$ 个元素可获得的最大价值。

$$dp[k][i] = Max( dp[k-1][j] + pre[j] \times ( pre[i] - pre[j])), j \in [k-1,i-1]$$

继续化简即可得到一个斜率不等式,而且是可以用单调队列优化的那种噢!

如果对斜率优化不清楚的话,可以参考我的另一篇博客:优化方法。

代码

// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (random_shuffle(c.begin(), c.end())), my_unique(c)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
int a[maxn];
ll pre[maxn], dp[2][maxn];

// inline double slope(int j, int k, int i) {
//   double mj = dp[(i & 1) ^ 1][j] - pre[j] * pre[j];
//   double mk = dp[(i & 1) ^ 1][k] - pre[k] * pre[k];
//   if (pre[j] == pre[k]) return (mj - mk) > 0 ? 10000 : -1e9 - 5;
//   return (mj - mk) / (pre[j] - pre[k]);
// }

bool check1(int j, int k, int i, int t) {
  ll mj = dp[(i & 1) ^ 1][j] - pre[j] * pre[j];
  ll mk = dp[(i & 1) ^ 1][k] - pre[k] * pre[k];
  return (mj - mk) <= pre[t] * (pre[k] - pre[j]);
}
bool check2(int j, int k, int f, int i) {
  ll mj = dp[(i & 1) ^ 1][j] - pre[j] * pre[j];
  ll mk = dp[(i & 1) ^ 1][k] - pre[k] * pre[k];
  ll mf = dp[(i & 1) ^ 1][f] - pre[f] * pre[f];
  return (mj - mk) * (pre[f] - pre[k]) >= (mk - mf) * (pre[k] - pre[j]);
}
int main() {
  /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
  */
  std::ios::sync_with_stdio(false);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", a + i), pre[i] = pre[i - 1] + a[i];
  for (int i = 1; i <= m; i++) {
    int l = 1, r = 1;
    vector<int> q(n + 2);
    q[1] = i - 1;
    for (int t = i; t <= n; t++) {
      while (l < r && check1(q[l], q[l + 1], i, t)) l++;
      int idx = q[l];
      dp[i & 1][t] = dp[(i & 1) ^ 1][idx] + pre[idx] * (pre[t] - pre[idx]);
      while (l < r && check2(q[r - 1], q[r], t, i)) r--;
      //   while (l < r && slope(q[r - 1], q[r], i) < slope(q[r], t, i)) r--;
      q[++r] = t;
    }
  }
  printf("%lld\n", dp[m & 1][n]);
}
最后修改:2020 年 07 月 30 日 10 : 55 PM