P14644 [POI 2025/2026 #1] 表达式 / Arithmetic expression

滥用评测者将被封号。

给定正整数 $n,a,b,c$。对于 $i=1,2,\ldots,n$，构造一个**代价**最小的表达式，使得表达式求值的结果为 $i$。只需要求出最小的代价。 --- 我们给出表达式及其代价的定义。 - $\texttt{1}$ 是代价为 $a$、求值结果为 $1$ 的表达式。 - 若 $X,Y$ 的代价分别为 $x,y$，且求值结果分别为 $p,q$： - $(X+Y)$ 是代价为 $x+y+b$、求值结果为 $p+q$ 的表达式。 - $(X\times Y)$ 是代价为 $x+y+c$、求值结果为 $p\cdot q$ 的表达式。 例如，$\tt(( 1 + 1) × (1 + 1)) × (1 + 1)$ 是代价为 $6a+3b+2c$，求值结果为 $8$ 的表达式。

一行四个正整数 $n,a,b,c$（$1\le n\le 3\, 000$，$1\le a,b,c\le10^9$）。

$n$ 个正整数，第 $i$ 个正整数表示求值结果为 $i$ 的表达式的最小代价。

### 样例解释 下表展示了可以得到 $1\sim 6$ 的最小代价的表达式。 | 求值结果 | 表达式 | 代价 | | :------ | :------------------ | :------------------------- | | $1$ | $\tt 1 $ | $a = 1$ | | $2$ | $\tt (1+1) $ | $2a + b = 2 + 4 = 6$ | | $3$ | $\tt ((1+1)+1) $ | $3a + 2b = 3 + 8 = 11$ | | $4$ | $\tt ((1+1)*(1+1)) $ | $4a + 2b + c = 4 + 8 + 2 = 14$ | | $5$ | $\tt (((1+1)*(1+1))+1)$ | $5a + 3b + c = 5 + 12 + 2 = 19$ | | $6$ | $\tt ((1+1)*((1+1)+1))$ | $5a + 3b + c = 5 + 12 + 2 = 19$ | ### 大样例 可以在附件中获得大样例。 样例 $\texttt{0a}$ 是题面中展示的样例。此外： * $\texttt{0b}$： $n = 9, a = 2, b = 3, c = 1$。 * $\texttt{0c}$： $n = 200, a = 1, b = 2, c = 3$。 * $\texttt{0d}$： $n = 2500, a = 1, b = 1, c = 1$。 * $\texttt{0e}$： $n = 3000, a = b = c = 10^9$。 ### 子任务 本题采用捆绑测试。 | 子任务编号 | 限制 | 得分 | | :---------: | :--------------------- | :-----: | | $1$ | $n \le 10$ | $13$ | | $2$ | $n \le 200$ | $31$ | | $3$ | $a = b = c = 1$ | $13$ | | $4$ | 无额外限制 | $43$ |