转移方程相当裸...完全是受下面的表格影响的

一个显然结论，某牛只可能连续时间带队，先换到后面再回来带队是无意义的

f[num,dis,spd,en] 表示 num 牛作为 Leader ，走了dis ,且这一时间段结束时速度为spd,且num牛剩余体力为en 时，所要花的最短时间
边界条件 f[i,0,0,e]=0   1<=i<=n
转移很好想：
1.前一时间段还是该牛带队 则

f1=min{f[num,dis-spd,k,en+spd*spd]}+1 
k满足 en+k*k+spd*spd<=e

2.前一时间是前一只牛带队 则

f2=min{f[num-1,dis-spd,k,e']}+1;

这种情况要求 e-en=dis-spd+spd*spd
e'满足 e'+dis-spd<=e
k满足 e'+k*k<=e

则 f=min{f1,f2}

时间复杂度是 0(N*D*E*V^2)  其中V为速度，速度小于E^（1/2)
所以约为 20*100*100*100=2*10^7 是可以接受的
至于空间...必须写滚动数组....

总之我是沙茶

• Re:沙茶写出4维DP...还MLE2次..最后是巨丑的滚动数组 (34) vongang 2012-08-13 15:33:44