「省选模拟赛」[hdu5171] 小奇的集合

2015年11月22日2,1560

注:原题没有考虑最大值为负数的情况

「题目背景」

小奇总是在数学课上思考奇怪的问题。

「问题描述」

有一个大小为n的可重集S,小奇每次操作可以加入一个数a+b(a,b均属于S),求k次操作后它可获得的S的和的最大值。(数据保证这个值为非负数)

「输入格式」

第一行有两个整数n,k表示初始元素数量和操作数,第二行包含n个整数表示初始时可重集的元素。

「输出格式」

输出一个整数,表示和的最大值。答案对10000007取模。

「样例输入」

2 2

3 6

「样例输出」

33

「数据范围」

对于30%的数据,有 n<=10^5,k<=10^5,|ai|<=10^5。

对于100%的数据,有 n<=10^5,k<=10^9,|ai|<=10^5。

题解

每次显然是选择最大和次大的元素相加,如果相加得到的数是集合的最大值,很容易就能写出递推式

K<=10^9显然是矩阵乘法加速

0 1 0           Fi-1                  Fi

1 1 0           Fi          =>       Fi+1

1 1 1           S                      S

特殊情况是集合的最大值和次大值可能为负数

1.只有次大值为负数,模拟若干次至其为正数再递推

2.两个都为负数,直接计算(每次都是这两个相加)

 

说点什么

提醒
avatar