APIO2010特别行动队commando_Here_is apio2010

【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就是最优决策。

本题实际上是比较简单的,想法也比较自然,只是思维过程还是比较复杂,本处就不一一赘述,只要多做此类的题就可以了。

最后一个小提示,除法的效率极低,耗时为乘法的几十倍,建议将一切除法改为乘法。


APIO2010特别行动队commando_Here_is apio2010

  

爱华网本文地址 » http://www.413yy.cn/a/25101015/284872.html

更多阅读

以色列独眼将军摩西达扬和他的漂亮女儿 摩西 以色列

以色列的独眼将军--达扬,以色列将军,政治家。1929年参加巴勒斯坦犹太人地下武装“哈加纳”,任战术教官。1937年加入英国人建立的“特别夜战队”,参与镇圧阿拉伯人的反英斗争。1939年“哈加纳”被宣布为非法组织后被捕。1941年获释后在

中国大陆各省市武警或特警突击队名称 猎鹰突击队女子特警队

济宁:猎鹰行动队、雷霆突击队、北京:雪豹突击队、蓝剑突击队上海:猎豹突击队重庆:闪电突击队、猎豹突击队、飞龙突击队黑龙江:老虎突击队、猎豹突击队吉林:虎豹突击队河南:雄狮突击队河北:红箭突击队保定:猎豹突击队陕西延安:黑鹰突

简介:特別攻撃隊或称“神风敢死队” 的由来 神风敢死队

简介:特別攻撃隊(或称"神风敢死队")的由来一、前言特别攻击队为旧日本帝国在二战时期,本土决战防卫的特殊战术,主要分为:海上特别攻击队、空中特别攻击队,及其它特别攻击队等类别。特别攻击队(日语:特別攻撃隊),或称"神风敢死队",由旧日本海军中

王珂主演的电视剧 演员王珂演过的电视剧

女子炸弹部队3狼穴主演:王珂,王新,周楚楚,林爽剧情:日本侵华战争全面爆发,为巩固占领,日军决定成立细菌武器工厂。女子行动队借机除掉731部队的研究员,并销毁新型细菌武器。成功铲除日军尾随而来的杀手,顺利保卫马远..

声明:《APIO2010特别行动队commando_Here_is apio2010》为网友蝴蝶兰州悠悠过分享!如侵犯到您的合法权益请联系我们删除