{"problem":{"name":"[NOI2023] 合并书本","description":{"content":"小 C 有 $n$ 本书，每本书都有一个重量，他决定把它们合并成一摞。 每一次合并小 C 可以把一摞书放到另一摞书上面，使得它们合并到一摞。如果小 C 把第 $i$ 摞书放到第 $j$ 摞书上面，小 C 需要消耗的体力为**第 $i$ 摞书的重量**加上**两摞书的磨损值之和**。 初始时每本书自成一摞且磨损值均为 $0$。每当小 C 将两摞书合并后，形成的新的一摞书的磨损值为合并前的两摞书的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9483"},"statements":[{"statement_type":"Markdown","content":"小 C 有 $n$ 本书，每本书都有一个重量，他决定把它们合并成一摞。\n\n每一次合并小 C 可以把一摞书放到另一摞书上面，使得它们合并到一摞。如果小 C 把第 $i$ 摞书放到第 $j$ 摞书上面，小 C 需要消耗的体力为**第 $i$ 摞书的重量**加上**两摞书的磨损值之和**。\n\n初始时每本书自成一摞且磨损值均为 $0$。每当小 C 将两摞书合并后，形成的新的一摞书的磨损值为合并前的两摞书的磨损值的**较大值的两倍再加一**，重量为合并前的两摞书的**重量之和**。\n\n你的任务是设计出合并的次序方案，使小 C 耗费的体力最少，并输出这个最小的体力耗费值。\n\n## Input\n\n**本题有多组测试数据。**\n\n输入的第一行包含一个正整数 $t$，表示数据组数。\n\n接下来依次输入每组测试数据，对于每组测试数据：\n\n输入的第一行包含一个正整数 $n$，表示有 $n$ 本书。\n\n输入的第二行包含 $n$ 个正整数，第 $i$ 个数 $w_i$ 表示第 $i$ 本书的重量。\n\n## Output\n\n对于每组测试数据输出一行一个整数，表示将 $n$ 本书合并成一摞需要消耗的最少体力。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n如果小 C 将 $4$ 本书两两合并再将得到的两摞合并成一摞，那么前两次需要消耗的体力值各为 $1$。第三次将一摞重量为 $2$ 的书放到另一摞上面，两摞书磨损值各为 $1$，需要消耗的体力为 $2 + 1 + 1 = 4$。\n\n因此如果选择这个方案，小 C 耗费的体力只有 $1 + 1 + 4 = 6$。\n\n可以证明，在上述例子中，$6$ 为最小的体力耗费值。\n\n**【数据范围】**\n\n对于所有测试数据保证：$1 \\le t \\le 10$，$1 \\le n \\le 100$，$1 \\le w_i \\le 10 ^ 9$。\n\n|测试点编号|$n \\le$|是否有特殊性质|\n|:-:|:-:|:-:|\n|$1 \\sim 2$|$7$|否|\n|$3$|$11$|否|\n|$4$|$13$|否|\n|$5 \\sim 6$|$22$|否|\n|$7 \\sim 8$|$28$|否|\n|$9 \\sim 13$|$50$|否|\n|$14$|$60$|否|\n|$15$|$70$|否|\n|$16$|$80$|否|\n|$17 \\sim 18$|$100$|是|\n|$19 \\sim 20$|$100$|否|\n\n特殊性质：保证 $w_i = 1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9483","tags":["搜索","2023","NOI","O2优化"],"sample_group":[["1\n4\n1 1 1 1\n","6\n"],["见附件中的 book/book2.in。","见附件中的 book/book2.ans。"],["见附件中的 book/book3.in。","见附件中的 book/book3.ans。"],["见附件中的 book/book4.in。","见附件中的 book/book4.ans。"]],"created_at":"2026-03-03 11:09:25"}}