http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1342. 能量棒(王钦石)
时间限制:3.0s   内存限制:256.0MB  
总提交次数:97   AC次数:9   平均分:41.70
将本题分享到:
   
 
问题描述
  小W是一个杰出的登山家。一天,他独自挑战一座神秘的山峰,也许是受到了诅咒,他不小心将背包掉落山崖。他摸了摸口袋,发现只剩下一根能量棒。
  能量棒被分为N个格子,每个格子上有一个正整数Ai,作为一个登山家,小W清楚他应该把能量棒分割成恰好K段使用,且必须全部用完。他也清楚使用一段A值和为x的能量棒可以获得-x2+Bx+C个单位的能量。不过小W数学不好,他不知道应该如何分割能量棒以获得最多的能量,请你帮助小W解决这个问题。
输入格式
  第一行一个整数T,表示此测试点包含测试数据的组数;
  每个测试数据包含两行:
  第一行四个整数N,K,B,C,用空格隔开,如题目描述中所述;
  第二行用空格隔开的N个整数,分别表示每个格子的Ai
输出格式
  对于每个测试数据一行,表示这个测试数据中最多所能获得的能量。
样例输入
2
3 2 3 2
1 2 3
3 2 3 2
2 3 1
样例输出
4
2
数据规模及约定