记录编号	423254	评测结果	AAAAAAAAAA
题目名称	[郑州集训 2017]NOI模拟题2.2	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.549 s
提交时间	2017-07-11 13:14:08	内存使用	31.34 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2010;
char s[N];
int n,m,lim[N],dp[N][N*2];
//dp[i][j]表示满足前i个位置的限制，第i+1个位置消去了j个单位的最小步数
typedef double db;
db val[N*2];
struct segmen_tree{
	db Min[N*4];
	#define lc x<<1
	#define rc x<<1|1
	void build(int x,int l,int r){
		if (l==r){return void(Min[x]=val[l]);}
		int mid=(l+r)>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
		Min[x]=min(Min[lc],Min[rc]);
	}
	db query(int x,int l,int r,int L,int R){
		if (l>=L&&r<=R) return Min[x];
		int mid=(l+r)>>1;db ans=1e9;
		if (L<=mid) ans=min(ans,query(lc,l,mid,L,R));
		if (R>mid) ans=min(ans,query(rc,mid+1,r,L,R));
		return ans;
	}
}T[3];
void solve(){
	int size=n+5;
	for (int i=1;i<=m;i++){
		for (int k=0,j=0;k<=n*2;k+=3,j++) val[j]=dp[i-1][k]-k/3.0;
		T[0].build(1,0,size);
		for (int k=1,j=0;k<=n*2;k+=3,j++) val[j]=dp[i-1][k]-k/3.0;
		T[1].build(1,0,size);
		for (int k=2,j=0;k<=n*2;k+=3,j++) val[j]=dp[i-1][k]-k/3.0;
		T[2].build(1,0,size);
		for (int j=0;j<=n*2;j++){
			int tp=(lim[i]-2*j+300000)%3;
			if (2*j-lim[i]>=0){
				int x=min((2*j-lim[i])/3,j/2);
				dp[i][j]=min(dp[i][j],dp[i-1][0]+j-x);
			}
			int L=max(0,(lim[i]-2*j)/3);
			int R=j/2*3-2*j+lim[i];
			db val=R>=0?T[tp].query(1,0,size,L,R/3):1e9;
			dp[i][j]=min(dp[i][j],(int)round(val-(2*j-lim[i])/3.0)+j);
		}
		for (int j=n*2-1;j>=0;j--) dp[i][j]=min(dp[i][j],dp[i][j+1]);
	}
	printf("%d\n",dp[m][0]);
	exit(0);
}
int main()
{
	freopen("wu.in","r",stdin);
	freopen("wu.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%s",s+1);
		for (int j=1;j<=m;j++)
			if (s[j]=='*') lim[j]=max(lim[j],n-i+1);
	}
	for (int i=0;i<=m;i++)
	for (int j=0;j<=n*2;j++)
		dp[i][j]=1e9;
	dp[0][0]=0;
	solve();
	return 0;
}