记录编号	105718	评测结果	AAAAAAAAAA
题目名称	[POJ 2841] 航海游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.671 s
提交时间	2014-06-12 10:20:01	内存使用	5.47 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=1010,INF=0x7fffffff/2;
int N,M;//N行M列
char board[SIZEN][SIZEN]={0};
int f[SIZEN][2][SIZEN]={0};
int T[2][SIZEN]={0},a[SIZEN]={0};
char line[SIZEN];
int sa[SIZEN]={0},sp[SIZEN]={0};
int wheel[SIZEN]={0};
void reverse(int *s){//翻转s[1]~s[M]
	int i=1,j=M;
	while(i<j){
		swap(s[i],s[j]);
		i++,j--;
	}
}
void reverse(char *s){//翻转s[1]~s[M]
	int i=1,j=M;
	while(i<j){
		swap(s[i],s[j]);
		i++,j--;
	}
}
int cost(int k,bool flag,int j){
	return T[flag][k]+((j-k+1)*(j-k))/2+sp[j]-sp[k]-k*(sa[j]-sa[k]);
}
class POINT{
public:
	int x,y;//x其实就是下标
	bool flag;//命运之轮次数奇偶性
	void print(void){printf("(%intd %intd %d)",x,y,flag);}
};
int calc_Y(int k,int flag){
	return k*k-2*sp[k]+2*k*sa[k]+2*T[flag][k];
}
bool check(POINT a,POINT b,int k){//ab斜率是否大于k,其中b的横坐标一定比a大
	return (b.y-a.y)>k*(b.x-a.x);
}
class CONQUEUE{//斜率优化维护凸包,凸包是下凸的
public:
	deque<POINT> Q;
	void push(int x,int flag,int k){//将下标为x纳入考虑,并用斜率k维护凸包
		int y=calc_Y(x,flag);
		POINT temp;
		temp.x=x,temp.flag=flag,temp.y=y;
		while(Q.size()&&!check(Q.back(),temp,k)) Q.pop_back();
		Q.push_back(temp);
	}
	void maintain_front(int k){
		while(Q.size()>=2&&!check(Q[0],Q[1],k)) Q.pop_front();
	}
	int frontcost(int j){//刚才已经维护过了,计算走到j的最优解
		if(Q.empty()) return -1;
		return cost(Q.front().x,Q.front().flag,j);
	}
	void clear(void){
		Q.clear();
	}
};
CONQUEUE Q[2];
void DP_line(int f[2][SIZEN]){//这个函数需要指定line,T,a
	Q[0].clear(),Q[1].clear();
	memset(f,-1,sizeof(int)*2*SIZEN);
	for(int j=1;j<=M;j++){
		sa[j]=sa[j-1]+a[j];
		sp[j]=sp[j-1]+a[j]*j;
		wheel[j]=wheel[j-1]+(line[j]=='F');
		if(line[j]=='O'){//这是一块石头
			Q[0].clear(),Q[1].clear();
			continue;
		}
		int k=2*j+1+2*sa[j];//斜率
		for(int t=0;t<=1;t++){
			bool flag=t^(wheel[j-1]&1);
			if(T[t][j]==-1) continue;
			Q[flag].push(j,t,k);//这里新加入决策
		}
		Q[0].maintain_front(k),Q[1].maintain_front(k);
		for(int t=0;t<=1;t++){
			bool flag=t^(wheel[j]&1);
			f[t][j]=Q[flag].frontcost(j);
		}
	}
}
void prepare_line(int i){
	memcpy(line,board[i],sizeof(line));
	memset(T[0],-1,sizeof(T[0])),memset(T[1],-1,sizeof(T[1]));
	for(int t=0;t<=1;t++){
		for(int j=1;j<=M;j++){
			if(f[i+1][t][j]==-1) continue;
			if(line[j]=='O') continue;
			T[t][j]=f[i+1][t][j]+1;
			if(line[j]=='B') T[t][j]--;
			else if(line[j]=='S') T[t][j]++;
		}
	}
	for(int j=1;j<=M;j++){
		if(line[j]=='B') a[j]=-1;
		else if(line[j]=='S') a[j]=1;
		else a[j]=0;
	}
}
int g1[2][SIZEN]={0},g2[2][SIZEN]={0};
int DPmin(int a,int b){
	if(a==-1) return b;
	if(b==-1) return a;
	return min(a,b);
}
void DP(void){
	for(int i=1;i<=M;i++) if(board[N][i]=='H') f[N][0][i]=0;
	for(int i=N-1;i>=2;i--){
		prepare_line(i);
		DP_line(g1);
		reverse(line),reverse(T[0]),reverse(T[1]),reverse(a);
		DP_line(g2);
		for(int j=1;j<=M;j++){
			for(int t=0;t<=1;t++){
				f[i][t][j]=DPmin(g1[t][j],g2[t][M+1-j]);
			}
		}
	}
	int ans=INF;
	for(int i=1;i<=M;i++){
		if(board[1][i]!='H') continue;
		if(f[2][1][i]==-1) continue;
		ans=min(ans,f[2][1][i]+1);
	}
	if(ans==INF) printf("No solution\n");
	else printf("%d\n",ans);
}
void read(void){
	memset(f,-1,sizeof(f));
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) scanf("%s",&board[i][1]);
}
int main(){
	freopen("navigationgame.in","r",stdin);
	freopen("navigationgame.out","w",stdout);
	read();
	DP();
	return 0;
}