我是很少上网做题的，说的不对大家见谅......

这题刚开始时看见是DP的确有点悬念......

其实宋神牛交作业的地点有N个,首先按地点从小到大排序,如果要交第i个地点的作业，那么 宋神牛肯定要把1至i-1的作业或者先把i+1至n的作业做完才做第i个作业，这样才会有一个最优解。

所以可以列方程f=f+i地点和j地点的距离；

i,j是宋神牛已经做完1至i-1和j+1至n的作业，l记录是送神牛在第i位或者第j位。

还有f:=min(f,f+i地点和j地点的距离),因为宋神牛可能从i到j或者从j到i。

最后f就是是宋神牛最后做第i作业的最小时间，贪心一下就行了。。。。

不会做呀。。。

老宋太牛了

楼下你们都Orz错人了！！！

你们应该膜拜我！！！

我是南京金陵中学的陶文博。你们不会没听说过吧？

楼下的楼下的楼下是假冒的。

沙茶题留名……

我果然是见了神牛心就虚阿.

一个普普通通的DP交了10多次.

一定要在NOI之前适应眼前全是大牛名字的情况.

只能说我太沙茶了或者宋神牛太牛了.

囧.........................................................rz

汗,当初我也不会做

先去重,针对地点相同,时间不同的作业,保留时间最大的那个(因为交作业是不要时间的,交N份作业和交1份作业消耗时间都为0)

然后F[L,R,0]表示还有L~R的作业未交,当前宋神牛在L-1个地点上

F[L,R,1]表示还有L~R的作业未交,当前宋神牛在R+1个地点上

初始F[1,N,0]:=0;

然后从两边向中间DP

f[l,r,1]:=min(max(f[l,r+1,1]+d[r+2]-d[r+1],t[r+1]),max(f[l,r+1,0]+d[r+1]-d[l-1],t[r+1]));

f[l,r,0]:=min(max(f[l-1,r,1]+d[r+1]-d[l-1],t[l-1]),max(f[l-1,r,0]+d[l-1]-d[l-2],t[l-1]));

最后枚举一下最后交的作业位置

ans:=min(ans,max(f+d[i]-d,t[i])+abs(d[i]-k));

ans:=min(ans,max(f+d-d[i],t[i])+abs(d[i]-k));

Orz 宋神牛！NOI 2009满分的神牛！

底下的都是神牛……某菜留名……飘过……此楼勿删，留作纪念

orz宋神牛

Orz curimit 牛 ！！！

来膜拜宋神牛

Orz宋神牛

时间和地点换错了啊

膜拜众神牛

终于AC了！！！！！！！！！

引用陶文博神牛（不是楼下下的那个假的，是真的！）的原话：

如果有三个点i,j,k,i