hiho一下第91周《Events Arrangement》(前半部分)

题目大意

现在有一场持续时间为M的游乐会,在游乐会上有N种不同的表演节目,同一时间只能有一个节目进行表演。

每种节目最多可以表演K次,且每种节目具有自己的三个属性值a[i],b[i],c[i]

当一个节目在时间剩余p开始时,它会产生a[i]-(M-p)*b[i]的价值,这个节目会持续c[i]个单位时间。

此外由于最后有结束致辞,所以需要空出最后1个单位时间。

求问,怎么安排表演节目,可以使得产生的总价值最大。

解题思路

前半部分,通过道动态规划来计算每个物品的价值。

价值可以通过a[i]-(M-P)*b[i]表示。

其中只有P是变量,其他都为常量。所以用一个函数表示

f(p) = a[i]-(M-p)*b[i]    持续c[i]的时间。

= a[i]-M*b[i] + p*b[i]

       _______     _____

      A      B

分为AB部分,A部分对每种节目都是常量,B部分随活动开始时间改变。

选好一系列活动之后A部分价值以及确定,只需对B部分价值进行排序,使B部分价值最大。

用p[i]表示第i个活动开始时候的剩余时间。B部分的价值:

PriceB=p[i]*b[i];

i,j为2个相邻的活动

i-1,i,j,j+1。p在i和i-1之间。

交换i,j的位置只会改变p[i],p[j]

上一篇:spring mvc4:异常处理


下一篇:Struts相关