题目描述

题解

题目比较坑，有大小相同这一要求。

先想到的是一个 \(O(N^3)\) 的 DP，设 \(dp_i\) 表示到 \(i\) 的最大数量，有转移方程 \(dp_i = \max\limits_{1 \le j \le i - 1}\{dp_j + \max\limits_{j + 1 \le k \le i}\{s_kcnt_{s_k}^2\}\}\)，应该很好理解吧。

然后这个时间复杂度肯定过不去。

考虑优化，设 \(p_i\) 表示到 \(i\) 的转移点，如果 \(p_i\) 与 \(i\) 位置上的不同色，肯定不如同色的优。如果颜色不同我们一定可以向后修改 \(p_i\) 使得同样是在这一段区间内 \(s_i\) 出现的次数不变。

有了上面做铺垫，更改一下 \(dp\) 的定义，要求该区间内选择的 \(s_0 = s_i\)，同样能保证最优。

所以转移方程变成了这样：\(dp_i = \max\limits_{s_i = s_j}\{dp_{j - 1} + s_i(sum_i - sum_j + 1)^2\}\)，去掉了枚举 \(s_0\) 的那一循环，时间复杂度降至 \(O(n^2)\)。

~~然后就不会了~~

对于相同的颜色 \(sum_i - sum_j + 1\) 单调递增，则 \(s_i(sum_i - sum_j + 1)^2\) 单调递增，于是有决策单调性，根据 FlashHu 大佬的话，导函数递增求最大值采用单调栈，我们用单调栈维护转移位置。

具体的，对于决策点 \(p_1, p_2\)，若有 \(p_1 < p_2\) 且 \(f(p_1) > f(p_2)\)，则从 \(p_1\) 转移，也就是说越靠后的转移转移点越靠前。

于是在单调栈上二分位置。

注意要分颜色讨论。

#include <cstdio>
#include <deque>

#define int long long

const int N = 1e5 + 10;

int n;
int s[N], b[N], sum[N];
int dp[N];

int Check(int i, int t) {
  return dp[i - 1] + s[i] * t * t;
}

int BinarySearch(int ql, int qr) {
  int l = 1, r = n, res = n + 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (Check(ql, mid - sum[ql] + 1) < Check(qr, mid - sum[qr] + 1))
      l = mid + 1;
    else
      r = mid - 1, res = mid;
  }
  return res;
}

std::deque<int> stk[N];

signed main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%lld", &s[i]), sum[i] = ++b[s[i]];
  for (int i = 1; i <= n; ++i) {
    while (stk[s[i]].size() >= 2 && BinarySearch(stk[s[i]][stk[s[i]].size() - 2], stk[s[i]][stk[s[i]].size() - 1]) <= BinarySearch(stk[s[i]][stk[s[i]].size() - 1], i))
      stk[s[i]].pop_back();
    stk[s[i]].push_back(i);
    while (stk[s[i]].size() >= 2 && BinarySearch(stk[s[i]][stk[s[i]].size() - 2], stk[s[i]][stk[s[i]].size() - 1]) <= sum[i])
      stk[s[i]].pop_back();
    dp[i] = Check(stk[s[i]][stk[s[i]].size() - 1], sum[i] - sum[stk[s[i]][stk[s[i]].size() - 1]] + 1);
  }
  printf("%lld\n", dp[n]);
  return 0;
}

hello_world2005's blog

「JSOI2011」柠檬题解

题目描述

题解