JSOI2011 柠檬

DP

首先，最优的划分方案每个区间取的数必然是区间两端的数。那么就是很显然的斜率优化 DP。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
typedef long long LL;
#define int LL
const int MAXN = 1e5;
int n;
int a[MAXN | 1], dp[MAXN | 1], sum[MAXN | 1], lst[10005];
std::vector < int > s[10005];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline double slope(int x, int y) {
  return 1.0 * (dp[x - 1] + sum[x] * sum[x] * a[x] - dp[y - 1] - sum[y] * sum[y] * a[y]) / (a[x] * sum[x] - a[y] * sum[y]);
}
signed main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    sum[i] = sum[lst[a[i]]] + 1;
    lst[a[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    while (s[a[i]].size() >= 2 && slope(s[a[i]][s[a[i]].size() - 2], s[a[i]][s[a[i]].size() - 1]) <= slope(s[a[i]][s[a[i]].size() - 1], i)) s[a[i]].pop_back();
    s[a[i]].push_back(i);
    while (s[a[i]].size() >= 2 && slope(s[a[i]][s[a[i]].size() - 2], s[a[i]][s[a[i]].size() - 1]) <= 2 * (sum[i] + 1)) s[a[i]].pop_back();
    int j = s[a[i]].back();
    dp[i] = dp[j - 1] + a[i] * (sum[i] - sum[j] + 1) * (sum[i] - sum[j] + 1);
  }
  printf("%lld\n", dp[n]);
  return 0;
}