原题地址 http://poj.org/problem?id=2841
中文题意就直接复制applepi神犇的了……翻译技巧太好了orz……
题目大意：航海游戏你感兴趣么？想象你指挥着一艘NB的多桅帆船打算横穿一个从未有人穿越过的大洋，确切的说是从南岸开到北岸。在
大洋两岸都有很多港口，由于你要完成的是人类历史上不曾有的壮举……所以说你可以选择从任何一个港口出发以及到达任何一个港口。
当然了，你的船不能在岸上跑。
我们把大洋分成N * M（N, M≤1000）个方格。首先，作为勇敢无畏，一往无前的船长，你的船绝对不能往南走，而只能往北、东、西三个
方向走。往北走就意味着离目标更进一步，所以说你通常情况下只需要1个单位的时间就可以走到下一个格子；向东、西走就意味着踌躇
不前，所以说如果你之前已经连续向东西方向走了X格，这一步通常就需要X + 1个时间单位才能走一格。
你不想绕任何远路。所以说，一旦你离开了一个格子，你就永远不能再回来。
海里还有一些特殊的格子：
O：代表障碍物（Obstacles）。这样的格子里有暗礁，为了你的安全，你永远不能进入这些格子。
F：代表命运之轮（Fortune’s wheels）。一旦你踏上有命运之轮的格子，你的命运就会逆转。我们深知你作为一个OIER
连GF都找不到的囧境……所以说你必须在到达终点前经过奇数次命运之轮。
B：代表祝福之石（Blessing stones）。你进入这样的格子不花费任何时间（但请注意横向移动的步数照样累计）。
S：代表风暴之咒（Invocations of storm）。你进入这样的格子就需要两倍于通常的时间（同上）。
其他的通常格子用一个点表示。
输入数据的第一行和最后一行代表海岸，上北下南。海岸用H表示港口，一个点表示陆地。
好了，天亮了……请计算你至少需要多少时间才能完成这个任务。
算法1：
用dp[i,j,k,state]表示船到达i行j列，已经连续东西方向走了k格，现在已经经过的命运之轮的奇偶性为state的最小时间.则
状态显然是O(nm^2)的，转移显然是O(1)的，总时间复杂度O(nm^2)，不可接受……
算法2：
看一下算法1，光是状态数就已经不可接受了，怎么办？当然应该改进状态表示……
用dp[i,j,state]表示船刚刚从i-1行j列跑到了i行j列，现在经过命运之轮奇偶性为state所花的最小时间。则转移是:
dp[i,j]=min(dp[i-1,k]+w[k,j])+di,j
其中，w[i,j]表示从第i-1行k列到第i-1行j列所花费的时间。d[i,j]表示从第i-1行j列到第i行j列所花费的时间。我们发现，
这个转移是O(m)的，状态数是O(nm)的，总时间复杂度依然是O(nm^2)，依然不可接受。但这个dp方程为后面的优化
提供了可能。
算法3：
为了后面的推倒过程方便，列的坐标范围是0~m-1.sea[]表示第i-1行海面的情况，具体字母代表含义是和输入数据一样
的。
我们考虑如何计算w[j,i].
我们只考虑j<=i的情况，因为对于j>=i的情况只要把海面左右对掉，就等价于j<=i的情况了。
显然，如果海面什么都没有，w[j,i]=(i-j+1)*(i-j)/2.
那么，海面上神马东西可以对w造成影响呢？只有风暴之咒(S)和祝福之石(B).
风暴之咒的效果相当于额外付出进入这个格子一次的代价，祝福之石相当于少付出进入这个格子一次的代价。他们恰好效
果相反，因此我们只讨论风暴之咒的情况。祝福之石只要把加号变减号，减号变加号即可。
我们定义
ws[i]=sum(sea[j]=‘S’?j:0)0<=j<=i
cs[i]=sum(sea[j]=‘S’?1:0)0<=j<=i
则可以发现，用ws[i]-ws[j]-j*(cs[i]-cs[j])就可以表示新增加的费用了……不明白的话在纸上画一下就明白了……
因此
cost(j,i)=(i-j+1)(i-j)/2+(ws[i]-ws[j])-j(cs[i]-cs[j])-(wb[i]-wb[j])+j*(cb[i]-cb[j])
=(i-j+1)(i-j)/2+(ws[i]-wb[i])-(ws[j]-wb[j])-j(cs[i]-cb[i])+j*(cs[j]-cb[j])
令w[i]=ws[i]-wb[i] c[i]=cs[i]-cb[i]
则
cost(j,i)=(i-j+1)(i-j)/2+(w[i]-w[j])-j(c[i]-c[j])
我们试着观察有没有单调性之类的东西的存在……
如果对于某个特定的i，存在j1<j2且f[j1,state1]+cost[j1,i]<f[j2,state2]+cost[j2,i]，那么应该满足什么条件？
f[j1,state1]+cost[j1,i]<f[j2,state2]+cost[j2,i]
展开并化简之，我们可以得到：
((2f[j2,state2]+j2^2-2w[j2]+2j2c[j2])-(2f[j1,state1]+j1^2-2w[j1]+2j1c[j1]))/(2*(j2-j1))>c[i]+i
这是一个斜率式！这时斜率优化的模型已经十分明显了。而且，我们观察到c[i]+i随i上升单调不降（证明：
c[i]>=c[i-1]-1所以c[i]+i>=c[i-1]-1+(i-1)+1=c[i-1]+(i-1))。
如果把决策j映射到点p(2j,2f[j,state2]+j^2-2w[j]+2jc[j])上，那么上面的式子就像当于：
对于状态i，决策j1优于j2，当且仅当(p1,p2)的斜率大于c[i]+i
令式子左边的部分为slope(j1,j2)
考虑对于状态i，三个映射到的X坐标递增的决策点x<z<y.如果z是最优决策，则必定有
slope(z,y)>c[i]+i
slope(x,z)<c[i]+i
即slope(x,z)<slope(z,y)！
也就是说，所有可能成为最优决策的决策点组成了一个下凸的半凸壳！
而且，因为c[i]+i随i上升单调不降，所以可以用一个单调队列维护半凸壳，最优决策是X坐标最小的点。这样，插入新决
策点并维护凸壳、更新c[i]+i并维护凸壳、取得最优决策点都是均摊O(1)的。
这样转移的时间复杂度就变成均摊O(1)了……总时间复杂度为状态数O(nm)，达到理论下界。
这还没完，我们发现，我们还没考虑到命运之石这种东西呢……于是一个单调队列不够了……需要两个单调队列分别存储
经过奇数、偶数次命运之石的可行决策，当遇到命运之石的时候就交换两个队列。
至于障碍物（Obstacles）的处理就很简单了……直接清空两个队列>_<
注意上面只是j<i的情况的讨论……我们还需要就j>i的情况用同样方法再做一次斜率优化dp（只要把海面左右反转一下就
可以了）。
然后就是拍代码的问题了……代码比较蛋疼……各种恶心……而且这题数据很强，想用有bug的代码水过不那么容易……
几个注意点：1. n<=2的时候要特判。2.虽然所有数据都可以用longint存下，但算斜率（叉积）的时候是需要用int64强制
类型转换一下的，否则中间结果就溢出了……
代码 https://ideone.com/7hH3L