NOIP%5B ~我这水平……就不发题解了吧~

以 $t$ 为单位转移肯定MLE+TLE。

所以以卖出为单位转移。

设 $f(i)$ 为在得到第 $i$ 张牌之后卖出卡牌的总积分。 显然有

$$f(i)=\max_{j\le i}\left[f(j-1)+(c_i-c_j+1)^2\right] $$

其中 $c_i$ 为 $i$ 之前 $a_i$ 的出现次数，可以用桶预处理。

注意可以一拿到牌就卖出，所以 $j\le i$ 有等号。

有 $(c_i-c_j)^2$ 项，考虑斜率优化。 我当时把斜率优化忘光光了，喜提 $TLE~~60pts$

正文开始：对本人早已忘却的斜率优化的记忆恢复

中心思想：分离变量。将与i有关的量看作常量，与j有关的看作变量，此时搞个数据结构与变量有关的最大值即可。

在直线方程 $y=kx+b$ 中，$x,y$ 是变量。因此考虑将其化成 $y(j)=K(i)x(j)+B(i)$ 的形式。

稍加计算可得

$$\begin{aligned} K(i)&=2(c_i+1) \\ y(j)&=f(j-1)+c_j^2 \\ x(j)&=c_j \end{aligned} $$

则有 $f(i)=\max B(i)-(c_i+1)^2$

原问题转化为：

有一系列 $x(j), y(j)$，给定一个 $K(i)$，求在所有过 $(x(j), y(j))$，斜率为 $K(i)$ 的直线中截距最大的一个。

显然答案点一定在一个上凸壳中（见左侧）。否则一定有一点会比它更优（见右侧）。

用一个类似单调队列的东西确保斜率单调递减即可。

具体地：

// 注意：此代码仅为演示，不保证100%正确

struct item {
	int x, y;
	double k;
};

struct kddq {
	const double inf=123456789.0;
	deque<item> dq;
	
	bool cmp(double k1, double k2) {
		return k1 > k2;
	}
	
	void push_back(int x, int y){
		if (dq.empty()){
			dq.push_back(x, y, inf);
			return;
		}
		
		double k = 1.0 * (y-yq.back()) / (x-xq.back());
		while (!cmp(dq.back().k, k)){
			dq.pop_back();
			k = 1.0 * (y-yq.back()) / (x-xq.back());
		}
		
		kq.push_back(x, y, k);
	}
}

中午了，吃饭，走人。

lower_bound，启动！

2024.9.4 更新

更新啥更新，摸鱼去了