古董

题目描述

拍卖师准备了 N件古董进行拍卖。这些古董有以下重要特性：

· 陈列规则：所有古董按 1,…,N编号陈列在一条长廊中，每天拍卖师只能从长廊任一端取出一件古董拍卖。

· 升值效应：古董拍卖顺序直接影响成交价。若第 i件古董在第 a天拍卖，成交价为 V_i×a（Vi​ 为初始估价）。

· 价值分布：第 i件古董的初始估价 Vi​取决于其陈列位置——从入口端开始，第 i 个展柜内的古董估价为Vi​。

拍卖师需要制定最优拍卖顺序，最大化总成交额。请帮助他计算出古董全部售出后的最大收益。

输入格式

· 第一行：古董数量 N

· 接下来n行：古董初始估价序列V1​∼VN​

输出格式

· 一行整数表示最大总收益

输入样例

5

1

3

1

5

2

输出样例

43

说明提示

【数据范围】

1≤N≤2000

1≤Vi​≤1000

限制

时间限制：1000ms

内存限制：256MiB

括号

题目描述

给定一个整数 n。生成所有长度为 n 的合法括号序列，并按字典序升序输出。

合法括号序列定义：

1. 空字符串是合法的。

2. 若字符串 s 合法，则 (+s+) 合法。

3. 若字符串 s 和 t合法，则 s+t合法。

输入格式

输入一个整数n

输出格式

每行输出一个合法括号序列（按字典序升序）。若无解则不输出。

输入样例#1

2

输出样例#1

()  

输入样例#2

4

输出样例#2

(())  

()()  

输入样例#3

6

输出样例#3

((()))  

(()())  

(())()  

()(())  

()()()  

说明提示

【数据范围 】

· 1≤N≤20

· N 是偶数

限制

时间限制：1000ms

内存限制：256MiB

搬运水果

题目描述

在果园里，n堆果实排成一个环形，第 i 堆果实的重量为 ai​。果农需要将所有果实合并成一堆。合并规则如下：

· 每次只能合并相邻的两堆，新堆的重量为两堆重量之和

· 每次合并消耗的体力等于新堆的重量

· 合并后新堆与剩余堆仍保持环形排列

请设计合并顺序，求出合并全过程消耗的最小总体力与最大总体力。

输入格式

第一行：整数 n表示果实堆数
第二行：n 个整数a1​,a2​,…,an​，表示每堆果实的重量

输出格式

第一行：最小总体力消耗
第二行：最大总体力消耗

输入样例

4

4 5 9 4

输出样例

43

54

说明提示

【数据范围】

1≤n≤100

1≤ai​≤1000

限制

时间限制：1000ms

内存限制：256MiB

金字塔

题目描述

给定长度为 n 的字符串 s。
从 s 中提取子序列，组成 pyramid字符串的方法有多少种？
答案需对 10⁹+7取模后输出。

输入格式

第一行：一个整数n

第二行：一个字符串s

输出格式

输出组成 pyramidpyramid 的方法数（取模 10⁹+7）。

输入样例#1

5

pxxxx

输出样例#1

0

输入样例#2

10

pyyradmiid

输出样例#2

4

说明提示

【数据范围】

· 1≤N≤10⁵

· s 仅包含小写英文字母

限制

时间限制：1000ms

内存限制：256MiB