记录编号	144683	评测结果	AAAAWAWAWW
题目名称	1664.[POJ 2841] 航海游戏	最终得分	60
用户昵称	rpCardinal	是否通过	未通过
代码语言	C++	运行时间	0.955 s
提交时间	2014-12-25 13:33:47	内存使用	18.51 MiB

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

#ifdef _WIN32
    #define ll "%I64d"
#else
    #define ll "%lld"
#endif

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

long long getY1(long long i,long long x,bool t)
{return f[i+1][x][t]+x*(x-1)/2+1;}

long long getY2(long long i,long long x,bool t)
{return f[i+1][x][t]+x*(x+1)/2+1;}

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);
    memset(f,0x3f,sizeof(f));
    long long i,j,k,l,r,sum,num,ans=INF; bool t; char tt;
    scanf(ll ll,&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][i][0]=0;
    for (i=n-1;i>1;--i)
        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;}
                Y[j]=getY1(i,j,t)+sum-num*j;
                if (a[i][j]=='B') {sum+=j; ++num; --Y[j];}
                if (a[i][j]=='S') {sum-=j; --num; ++Y[j];}
                if (a[i][j]=='F') t=!t;
                if (a[i+1][j]!='O')
                {
                    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][j][t]=min(f[i][j][t],
                    Y[k]+j*(j-2*k+1)/2-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;}
                Y[j]=getY2(i,j,t)-sum+num*j;
                if (a[i][j]=='B') {sum+=j; ++num; --Y[j];}
                if (a[i][j]=='S') {sum-=j; --num; ++Y[j];}
                if (a[i][j]=='F') t=!t;
                if (a[i+1][j]!='O')
                {
                    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][j][t]=min(f[i][j][t],
                    Y[k]+j*(j-2*k-1)/2+sum-num*k);
            }
        }
    /*for (i=1;i<=n;++i)
    {
        for (j=1;j<=m;++j)
            printf("%2I64d,%2I64d ",f[i][j][0]==INF?-1:f[i][j][0],f[i][j][1]==INF?-1:f[i][j][1]);
            //printf("%2I64d ",f[i][j][0]==INF?-1:f[i][j][0]);
            //printf("%2I64d ",f[i][j][1]==INF?-1:f[i][j][1]);
        putchar('\n');
    }*/
    for (i=1;i<=m;++i)
    {
        if (a[1][i]!='H') continue;
        ans=min(ans,f[2][i][1]+1);
    }
    if (ans==INF) printf("No solution\n");
    else printf(ll "\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}