[R18E]重新粉刷 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

墙壁从左至右分成 $n$ 块，第 $i$ 块墙壁的颜色为 $a_i(1\leq a_i\leq n)$。

现在你要重新粉刷其中任意块（可以为 $0$ 块）墙壁，将第 $i$ 块墙壁粉刷为颜色 $x$ 需要花费 $a_i+x$ 元，其中 $x$ 可以是任意正整数。

对 $i=1\sim n-1$，分别求重新粉刷墙壁使得至少有 $i$ 对相邻墙壁颜色不同的最小花费。

格式

输入格式

第一行包含一个整数 $n$，表示墙壁的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每块墙壁的颜色。

输出格式

输出 $n-1$ 个整数，第 $i$ 个整数表示重新粉刷墙壁使得至少有 $i$ 对相邻的墙壁颜色不同的最小花费。

样例

样例输入 #1

6
4 4 4 2 3 3

样例输出 #1

0 0 4 5 9

样例解释 #1

一块墙壁都不重新粉刷时墙壁颜色分别为 $\{4,4,4,2,3,3\}$，有 $2$ 对相邻墙壁颜色不同：①第 $3$ 块墙壁和第 $4$ 块墙壁、②第 $4$ 块墙壁和第 $5$ 块墙壁。

将第 $5$ 块墙壁粉刷为颜色 $1$ 花费 $3+1=4$ 元。完成粉刷后墙壁颜色分别为 $\{4,4,4,2,1,3\}$，有 $3$ 对相邻墙壁颜色不同：①第 $3$ 块墙壁和第 $4$ 块墙壁、②第 $4$ 块墙壁和第 $5$ 块墙壁、③第 $5$ 块墙壁和第 $6$ 块墙壁。

将第 $2$ 块墙壁粉刷为颜色 $1$ 花费 $4+1=5$ 元。完成粉刷后墙壁颜色分别为 $\{4,1,4,2,3,3\}$，有 $4$ 对相邻墙壁颜色不同：①第 $1$ 块墙壁和第 $2$ 块墙壁、②第 $2$ 块墙壁和第 $3$ 块墙壁、③第 $3$ 块墙壁和第 $4$ 块墙壁、④第 $4$ 块墙壁和第 $5$ 块墙壁。

将第 $2$ 块墙壁粉刷为颜色 $1$，第 $5$ 块墙壁粉刷为颜色 $1$，共花费 $(4+1)+(3+1)=9$ 元。完成粉刷后墙壁颜色分别为 $\{4,1,4,2,1,3\}$，有 $5$ 对相邻墙壁颜色不同：①第 $1$ 块墙壁和第 $2$ 块墙壁、②第 $2$ 块墙壁和第 $3$ 块墙壁、③第 $3$ 块墙壁和第 $4$ 块墙壁、④第 $4$ 块墙壁和第 $5$ 块墙壁、⑤第 $5$ 块墙壁和第 $6$ 块墙壁。

数据规模

对于 $20\%$ 的数据，$n\leq 50$。

对于 $50\%$ 的数据，$n\leq 400$。

对于 $100\%$ 的数据，$1\leq n\leq 3000$，$1\leq a_i\leq n$。