信息学集训队作业0096-cow cycling

题目0096–CowCycling（奶牛蹬车队）题目来源：Usaco02feb推荐者：刘汝佳英文原文CowCyclingThecowbicyclingteamconsistsofN(1<=N<=20)cyclists.Theywishtodeterminearacestrategywhichwillgetoneofthemacrossthefinishlineasfastaspossible.Likeeveryoneelse,cowsracebicyclesinpacksbecausethat'sthemostefficientwaytobeatthewind.Whiletravellingatxlaps/minute(xisalwaysaninteger),theheadofthepackexpendsx*xenergy/minutewhiletherestofpackdraftsbehindhimusingonlyxenergy/minute.Switchingleadersrequiresnotimethoughcanonlyhappenafteranintegernumberofminutes.Ofcourse,cowscandropoutoftheraceatanytime.ThecowshaveenteredaraceD(1<=D<=100)lapslong.Eachcowhasthesameinitialenergy,E(1<=E<=100).Whatisthefastestpossiblefinishingtime?Onlyonecowhastocrosstheline.Thefinishtimeisaninteger.Overshootingthelineduringsomeminuteisnodifferentthanbarelyreachingitatthebeginningofthenextminute(thoughthecowmusthavetheenergylefttocycletheentireminute).N,D,andEareintegers.InputAsinglelinewiththreeintegers:N,E,andDOutputAsinglelinewiththeintegerthatisthefastestpossiblefinishingtimeforthefastestpossiblecow.Output0ifthecowsarenotstrongenoughtofinishtherace.SampleInput33020SampleOutput7NoteontheSampletimeleaderPackspeedTotaldistLeaderEusedthisminute1155252127432*4111642213453*3169632184732204*=leaderswitch二、中文翻译三、初步讨论情况项荣璟没有在普通动态规划的基础上有超越。姜尚仆动态规划，但是优化很困难。伍昱Dp的效果很不理想周源动态规划我想过，具体优化没有想仔细。雷环中原题的DP是比较容易的，不过优化还需要进一步思考。张宁本题可以通过动态规划解决，并且可以进行一些优化刘才良两次动态规划可做，但复杂度很高刘一鸣我自己设计的DP，复杂度较高，时间比较长，很希望聆听高手的指教。方奇两次动态规划，复杂度为O(N*E^2)王知昆只会O(N^3)的张云亮我认为动态规划也已经够了，以当前有几只牛，圈数，带头牛的体力作为状态，也只有20*100*100*10邵煊程最优方案必是奶牛1，2，…，n依次领骑，最后奶牛n撞线，设f[l，r，c]表示完成c圈，领骑的是奶牛l，它还剩r个单位精力。则f[l，r，c]=min{f[l，r+x2，c-x]+1（0<x<=c，表示最近一次奶牛l领跑的速度是每分钟x圈），f[l-1，y，c-x]（y>=0，E-（c-x）-x2=r，表示奶牛l刚开始领跑的情况）。由于其中有许多不必要的计算，应该可以优化，但约束条件好像不容易找到。饶向荣动态规划:f[i,j]表示已有个骑手领先跑圈的最少时间。那么递推方程为：f[i,j]=min{f[i-1,k]+mc[full-k,j-k]}其中表示用体力跑圈所用的最少时间。为最开始的体力。此递推过程的复杂度为O(n*d2)。而mc[a,b]可预先求出来。求他的复杂度不大于O(n*d2)。所以总的复杂度为O(n*d2),空间复杂度O(N2)。金恺动态规划（二维描述）：先考虑一个人单独骑的情况，设Onei,j表示花去不超过j的能量，最少需要多少时间才能走完长为i或更多的距离，显然有如下的转移方程：。再考虑多个人一起骑：可以先让#1领骑，再让#2领骑，……。设Morei,j表示一共让i个人先后领骑，走完j个单位长度最少需要多少时间，容易推出下列转移方程：Morei,j=Min{Morei-1,k+Onej-k,E-k}其中E为初始能量。上述算法的时空复杂度分别为、DE。优化：在求Onei,j时，先令Onei,j=Onei+1,j，再求路程刚好是i，能量不超过j的最少用时：也就是求最小的t存在正整数数列a1,a2,…,at使得。不难想到：当其中有两个数ax,ay满足ax–ay>1时，可以令a’xax–1,a’yay+1，此时有a’x+a’y=ax+ay、a’x2+a’y2<ax2+ay2，因此，可以令序列a尽量的平均（任一两数之差为0或1）。那么，如果枚举t的值就可以根据①求出序列a（可设a1≥a2≥…≥at因为顺序是任意的），然后根据②判断是否可行——这只要O(1)就行了。t是否需要枚举呢？No！根据前面的转移方程可得Onei,j≤Onei+1,j，也就是t≤Onei+1,j，而如果t不存在解，t–1也不会存在（可用反证法证明），这样一来只要先令tOnei+1,j再不断减少就可以了求出t了。求Onei,j是复杂度就降为了O(DE)。Morei,j化简就复杂多了：我试图证明四边形不等式：Onea+1,b+Onea+1,b+1≤Onea+2,b+1+Onea,b或是Morea,b+Morea–1,b–1≤Morea–1,b+Morea,b–1是否成立，但是都找到了反例。因此总复杂度仍有O(DE+ND2)何林设f[i,j]表示i头奶牛总共领跑j圈需要的时间。g[i,j]表示一头还有i单位个精力的奶牛总共领跑j圈需要的时间。方程是：f[i,j]=f[i-1,p]+g[e-p,j-p]g[i,j]用均值不等式就能算出来。求f[n,d]o(n3)的复杂度即可。n<=100，我觉得非常快啊。