营救小灿

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

小灿在被做成食品之前,重情重义的刘宝宝早就赶到了机器所在地旁边的山的山峰上,现在山峰上有许多的石子排成了1排(不要在乎为什么山峰上可以有一排石子),他们的重量都为1,刘宝宝很懒,他只会把相邻的石子合并在一起,已知合并石子的要耗费刘宝宝石子重量和的体力,还是因为刘宝宝很懒,所以刘宝宝只会耗费最小的体力来合并所有的石子,又是因为刘宝宝很懒,他想让你来算算这个消耗的体力值。当然最后推石头下山是你来推hahaha。

Description

有n个石头排成一排,第i个重量为1,每次可以合并相邻两堆石子,需要的体力为两堆重量之和,新的一堆石子的重量也为两堆石子的重量和,求:将这n个石子合并为一堆需要的体力和的最小值。

Input

一个数n,表示有n个石子

Output

一个数ans,表示最少的体力消耗
了防止因为答案太大从而爆int/long long, 请大家使用unsigned long long 数据类型,
采取自然溢出的方法对2^64取膜(自然溢出就是你不需要取膜)。

Sample 1

Input

4

Output

8

Limitation

1000ms, 512MB

Hint

5% n<=5
30% n<=100
45% n<=2333
60% n<=100000
100% n<=10^15

后记

小灿被刘宝宝救出后,小铭感到自己队友的弱小,他决定自己来迎战刘宝宝,刘宝宝带了

noip每天第1题难度题比赛

未参加
状态
已结束
规则
OI
题目
3
开始于
2017-11-04 14:00
结束于
2017-11-04 18:00
持续时间
4.0 小时
主持人
参赛人数
9