不会做呀。。。

老宋太牛了

楼下你们都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