传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小Z想把若干个 1 使用加法、乘法两种规则拼接为一个表达式，其中使用一次加法的花费为 b，使用一次乘法的代价为 c，使用单独一个数字 1 也需要花费 a。

求得可以使表达式结果为 i 的最小花费。

例如， $\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$ ）。分别表示初始 1 的最大个数、三种操作的相应花费。

输出格式

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

输入输出样例

6 1 4 2

1 6 11 14 19 19

样例 $\tt \#1$ 说明

下表展示了可以得到 $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$

数据范围

本题采用捆绑测试。

子任务编号	限制	得分
$1$	$n \le 10$	$10$
$2$	$n \le 200$	$30$
$3$	$a = b = c = 1$	$10$
$4$	无额外限制	$50$

【AC-011-Div3】算法组月赛 || Round · 11

状态: 已结束
规则: OI
题目: 4
开始于: 2026-5-23 0:00
结束于: 2026-5-25 0:00
持续时间: 48 小时
主持人: Kayla
参赛人数: 3