题目描述
blablabla
样例
blablabla
(单调栈) $O(n)$
$dp[i] = dp[j - 1] + a[i] * (sum[i] - (sum[j] - 1)) ^ 2$
$dp[i] = dp[j - 1] + a[i] * (sum[i] ^ 2 - 2 * sum[i] * (sum[j] - 1) + (sum[j] - 1) ^ 2)$
若 $j < k$
$dp[j - 1] + a[i] * (sum[i] ^ 2 - 2 * sum[i] * (sum[j] - 1) + (sum[j] - 1) ^ 2)$
$<$
$dp[k - 1] + a[i] * (sum[i] ^ 2 - 2 * sum[i] * (sum[k] - 1) + (sum[k] - 1) ^ 2)$
$dp[j - 1] - a[i] * 2 * sum[i] * sum[j] + a[i] * (sum[j] - 1) ^ 2$
$<$
$dp[k - 1] - a[i] * 2 * sum[i] * sum[k] + a[i] * (sum[k] - 1) ^ 2$
又∵ $a[i] = a[j] = a[k]$
∴$(dp[j - 1] + a[j] * (sum[j] - 1) ^ 2) - (dp[k - 1] + a[k] * (sum[k] - 1) ^ 2) < 2 * a[i] * sum[i] * (sum[j] - sum[k])$
令 $Query (j) = dp[j - 1] + a[j] * (sum[j] - 1) ^ 2$
$∴K = \frac{Query (j) - Query (k)}{sum[j] - sum[k]}$
若 $K >= 2 * a[i] * sum[i]$ 则 $w[j] < w[k]$
若 $K <= 2 * a[i] * sum[i]$ 则 $w[j] > w[k]$
C++ 代码
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define LL long long
#define ULL unsigned long long
#define qc q[colour]
template <typename T> void read (T &x) {x = 0; T f = 1;char tem = getchar ();while (tem < '0' || tem > '9') {if (tem == '-') f = -1;tem = getchar ();}while (tem >= '0' && tem <= '9') {x = (x << 1) + (x << 3) + tem - '0';tem = getchar ();}x *= f;}
template <typename T> void write (T x) {if (x < 0) {x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
const int Maxn = 1e5 + 15;
const int Inf = 0x3f3f3f3f;
int n;
int a[Maxn], bak[Maxn];
LL dp[Maxn], sum[Maxn];
vector <int> q[Maxn];
LL Query (int j) {
return dp[j - 1] + a[j] * (sum[j] - 1) * (sum[j] - 1);
}
double Get_K (int j, int k) {
return (double)(Query (j) - Query (k)) / (sum[j] - sum[k]);
}
void add (int colour, int Index) {
int len = qc.size ();
while (len > 1 && Get_K (qc[len - 2], qc[len - 1]) <= Get_K (qc[len - 2], Index)) {
qc.pop_back ();
len = qc.size ();
}
qc.push_back (Index);
}
LL Get_Dp (int i, int j) {
return dp[j - 1] + a[i] * (sum[i] - sum[j] + 1) * (sum[i] - sum[j] + 1);
}
signed main () {
read (n);
for (int i = 1; i <= n; i++) {
read (a[i]);
bak[a[i]]++;
sum[i] = bak[a[i]];
}
for (int i = 1; i <= n; i++) {
add (a[i], i);
int colour = a[i];
int len = qc.size ();
while (len > 1 && Get_K (qc[len - 2], qc[len - 1]) <= 2 * a[i] * sum[i]) {
qc.pop_back ();
len = qc.size ();
}
dp[i] = Get_Dp (i, qc[len - 1]);
}
write (dp[n]);
return 0;
}
%%%