记录编号	144727	评测结果	AAAAAAAAAA
题目名称	[POJ 2841] 航海游戏	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.595 s
提交时间	2014-12-26 17:17:26	内存使用	1.18 MiB

/* 斜率优化DP 14.12.25 */

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f3f3f3fll
using namespace std;

long long n,m,f[2][1010][2],q[1010],Y[1010];
char a[1010][1010];

bool cmp0(long long i,long long x,long long y,long long z)
{return (Y[x]-Y[y])>z*(x-y);}

bool cmp1(long long i,long long x,long long y,long long z)
{return (Y[x]-Y[y])*(y-z)>(Y[y]-Y[z])*(x-y);}

bool cmp2(long long i,long long x,long long y,long long z)
{return (Y[x]-Y[y])*(y-z)<(Y[y]-Y[z])*(x-y);}

int main()
{
    freopen("navigationgame.in","r",stdin);
    freopen("navigationgame.out","w",stdout);
    long long i,j,k,l,r,sum,num,ans=INF,C; bool t; char tt;
    memset(f,0x3f,sizeof(f));
    scanf("%lld%lld",&n,&m);
    for (i=1;i<=n;++i) scanf("%s",a[i]+1);
    for (i=1;i<=m;++i) if (a[n][i]=='H') f[n&1][i][0]=0;
    for (i=n-1;i>1;--i)
    {
        for (j=1;j<=m;++j) f[i&1][j][0]=f[i&1][j][1]=INF;
        for (tt=0;tt<=1;++tt)
        {
            l=r=sum=num=0; t=tt;
            for (j=1;j<=m;++j)
            {
                if (a[i][j]=='O') {l=r=0; continue;} C=1;
                if (a[i][j]=='B') {sum+=j; ++num; C=0;}
                if (a[i][j]=='S') {sum-=j; --num; C=2;}
                Y[j]=f[!(i&1)][j][t]+((j*(j-1))>>1)+sum-num*j+C;
                if (a[i][j]=='F') t=!t;
                if (a[i+1][j]!='O'&&Y[j]*2<INF)
                {
                    while (l+1<r&&cmp1(i,q[r-1],q[r],j)) --r;
                    q[++r]=j;
                }
                if (l==r) continue;
                while (l+1<r&&cmp0(i,q[l+1],q[l+2],j-num)) ++l;
                k=q[l+1]; f[i&1][j][t]=min(f[i&1][j][t],
                    Y[k]+((j*(j-2*k+1))>>1)-sum+num*k);
            }
            l=r=sum=num=0; t=tt;
            for (j=m;j>=1;--j)
            {
                if (a[i][j]=='O') {l=r=0; continue;} C=1;
                if (a[i][j]=='B') {sum+=j; ++num; C=0;}
                if (a[i][j]=='S') {sum-=j; --num; C=2;}
                Y[j]=f[!(i&1)][j][t]+((j*(j+1))>>1)-sum+num*j+C;
                if (a[i][j]=='F') t=!t;
                if (a[i+1][j]!='O'&&Y[j]*2<INF)
                {
                    while (l+1<r&&cmp2(i,q[r-1],q[r],j)) --r;
                    q[++r]=j;
                }
                if (l==r) continue;
                while (l+1<r&&cmp0(i,q[l+1],q[l+2],j+num)) ++l;
                k=q[l+1]; f[i&1][j][t]=min(f[i&1][j][t],
                    Y[k]+((j*(j-2*k-1))>>1)+sum-num*k);
            }
        }
    }
    for (i=1;i<=m;++i)
    {
        if (a[1][i]!='H') continue;
        ans=min(ans,f[0][i][1]+1);
    }
    if (ans==INF) printf("No solution\n");
    else printf("%lld\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}