Toggle navigation
清远信息技术在线课堂判题系统
F.A.Qs
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
Language
中文
ئۇيغۇرچە
English
فارسی
ไทย
한국어
Problem1002--A-Scape遇上暴力题
1002: A-Scape遇上暴力题
[Creator :
]
Time Limit :
20.000
sec
Memory Limit :
512 MB
Submit
Solved: 0
Submit Num: 4
Statistics
Description
绿意盎然的一天,Scape去XX赛区加冕为王。
Scape倒开题目,看到了这样一道题:
有一个序列 A 和 L,R ,每次可以合并相邻的 K 个元素(要求 L<=K<=R ),代价为这 K 个元素的和并合并产生一个新元素,权值为这 K 个元素的和。
求把整个序列合并为一个元素的最小代价。
T 组数据, T<=10, n<=300 。
Scape 想都不想就写了一个 n^4 暴力,结果居然 T 了,作为 XX 之王的 Scape 自然不会管这种辣鸡题,请你写出这道题。
Input
第一行一个整数 T(T<=10) ,表示数据组数。
每组数据第一行三个整数 n,L,R 表示序列 A 的长度,和 K 的上下界限制。
第二行 n 个整数表示序列 A 。
Output
每行一个整数表示结果,无解输出 0。
Sample Input
Copy
3 3 2 2 1 2 3 3 2 3 1 2 3 4 3 3 1 2 3 4
Sample Output
Copy
9 6 0
HINT
数据范围
对于 20% 的数据, n<=20 。
对于 60% 的数据, n<=50 。
对于 100% 的数据, n<=300,Ai<=100 。
Source/Category
BJWC2018
NOIP
高级