记录编号	323410	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]瑰丽华尔兹	最终得分	100
用户昵称	派特三石	是否通过	通过
代码语言	C++	运行时间	0.345 s
提交时间	2016-10-16 17:13:43	内存使用	0.48 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define pa 	system("pause")
const int maxn=210;
using namespace std;
char g[maxn][maxn];int n,m,ax,ay,p,f[2][maxn][maxn],ans=0,dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1},deq[maxn],pos[maxn];bool tt=0;
void work(int x,int y,int edge,int type,int l)//坐标，边界，第几次倾斜，操作种类，区间长度 
{
	int s=1,e=0;//队列起点，终点 
	for(int i=1;i<=edge;++i)
	{
		if(g[x][y]=='.')
		{
			int v=f[!tt][x][y]-i;//类似单调队列优化多重背包，拉到同一水平再比较 
			while(s<=e&&deq[e]<v)--e;
			deq[++e]=v;pos[e]=i;
			while(i-pos[s]>l)++s;//失效 
			f[tt][x][y]=deq[s]+i;
		}
		else
		{
			s=1,e=0;//清空队列 
			f[tt][x][y]=-0x7f7f7f7f;//家具，无法到达 
		}
		x+=dx[type],y+=dy[type];
	}
}
int Main()
{
	freopen("adv1900.in","r",stdin);
	freopen("adv1900.out","w",stdout);
    scanf("%d%d%d%d%d",&n,&m,&ax,&ay,&p);
    for(int i=1;i<=n;++i)scanf("%s",g[i]+1);
   for(int i=1;i<=n;++i)
   		for(int j=1;j<=m;++j)f[0][i][j]=-0x7f7f7f7f;   //无法确定每次的转移，每次枚举所有位置，为了确定由起点出发，所以起点与其他点初始值必须相差较大 
	f[0][ax][ay]=0;
	tt=0;
    for(int i=1;i<=p;++i)
    {
		int s,t,d;
        scanf("%d%d%d",&s,&t,&d);
        tt=!tt;
        if(d==1)for(int j=1;j<=m;++j)work(n,j,n,1,t-s+1);
        if(d==2)for(int j=1;j<=m;++j)work(1,j,n,2,t-s+1);
        if(d==3)for(int j=1;j<=n;++j)work(j,m,m,3,t-s+1);
        if(d==4)for(int j=1;j<=n;++j)work(j,1,m,4,t-s+1);
    } 
    for(int i=1;i<=n;++i)
    	for(int j=1;j<=m;++j)ans=max(ans,f[tt][i][j]);
    printf("%d\n",ans);
} 
int start=Main();
int main(){;}