【APIO2010】特别行动队
题目简述:一只--队伍中有N个士兵,每个人的战斗力xi,现要将士兵划分为若干组,每组的人为连续的一串,整个组的初始战斗力所有人之和y,修正后的战斗力y’=A*y^2+B*y+C,(A,B,C为已知常数,A<0)。总的战斗力为所有组的修正战斗力之和。要求最大化总战斗力。(N<=10^6)
题目简析:很明显是动规的题目。
用f[i]表示从1到i划分为若干组能取得的最大战斗力。
f[i]=max{f[j]+G(si-sj)}。(0<=j<i)
其中si为1到i的战斗力之和,G(x)=A*x^2+B*x+C;
直接动规O(n^2),预计40~50分。
利用G函数贪心,预计最高70分。
这种1D/1D的方程可以用斜率优化。
设有决策j,k。其中j为i的最优决策,k为除j外任意决策。
则f[j]+A*(si-sj)^2+B*(si-sj)+C>=f[k]+A*(si-sk)^2+B*(si-sk)+C
=>f[j]-f[k]+A*sj*sj-A*sk*sk-B*sj+B*sk>=2A*si*(sj-sk)
当j<k时,(f[j]-f[k]+A*sj*sj-A*sk*sk-B*sj+B*sk)/(sj-sk)<=2A*si
令H[j,k]= (f[j]-f[k]+A*sj*sj-A*sk*sk-B*sj+B*sk)/(sj-sk)。
即当j<k时,如果H[j,k]<=2A*si,则决策j不差于k;H[j,k]>=2A*si,k不差于j。
依据此函数与2A*si的比较就可知两个决策的优劣。
然后维护一个决策值序列d,其中d1<d2<d3<……<dk。满足H[d1,d2]>=H[d2,d3]>=……>=H[dk-1,dk]。
因为如果出现H[d1,d2]<H[d2,d3],考虑H[d2,d3]与2A*si的关系。
如果H[d2,d3]>2A*si,则d3比d2优,随着i的递增,2A*si递减,仍然满足H[d2,d3]>2A*si,这样d3永远比d2优。
如果H[d2,d3]<=2A*si,则H[d1,d2]<2A*si,这样d1比d2优;并且随着i的递增,2A*si递减,对于某一个i,可能H[d1,d2]<=2A*si<=H[d2,d3],这样,d1,d3都比d2优;如果是2A*s1<=H[d1,d2]<H[d2,d3],这样是d3比d2优。
总而言之,只要出现了这种情况,d2就一定不会成为最优决策,可以删去。
每次在队首剔除H[dl,dl+1]>2*A*si的决策,直至H[dl,dl+1]恰好小于等于2A*si,此时的dl就是最优决策。
本题实际上是比较简单的,想法也比较自然,只是思维过程还是比较复杂,本处就不一一赘述,只要多做此类的题就可以了。
最后一个小提示,除法的效率极低,耗时为乘法的几十倍,建议将一切除法改为乘法。