#单调队列#JZOJ 1753 锻炼身体

题目

一个(n*m)的矩阵，有些格子不能经过，有(k)个时段，
要么停留某个格子，要么沿时段规定的方向移动，问最多能够移动多少次
(n,m,kleq 200)

---

分析

题目已经提示了(O(nmk))，考虑朴素的搜索为(O(n^2mk))的，
考虑用单调队列优化此过程使复杂度降至1s内

---

代码

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define rr register
using namespace std;
const int N=201; struct rec{int l,r,opt;}ques[N];
int n,m,zx,zy,Q,q[N],dp[N][N],f[N][N],a[N][N],ans;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline signed max(int a,int b){return a>b?a:b;}
bool cmp(rec x,rec y){return x.l<y.l;}
signed main(){
	n=iut(),m=iut(),zx=iut(),zy=iut(),Q=iut();
	memset(dp,0xcf,sizeof(dp)),dp[zx][zy]=0;
	for (rr int i=1;i<=n;++i)
	for (rr int j=1;j<=m;++j){
		rr char c=getchar();
		while (c!='.'&&c!='x') c=getchar();
		a[i][j]=c=='.';
	}
	for (rr int i=1;i<=Q;++i)
	    ques[i]=(rec){iut(),iut(),iut()};
	sort(ques+1,ques+1+Q,cmp);
	for (rr int T=1;T<=Q;++T){
		rr int len=ques[T].r-ques[T].l+1,head,tail;
		memcpy(f,dp,sizeof(dp));
		switch (ques[T].opt){
			case 1:{
				for (rr int j=1;j<=m;++j){
				    head=1,tail=0;
					for (rr int i=n;i>=1;--i){
						if (!a[i][j]){
							head=1,tail=0;
						    continue;
						}
						while (head<=tail&&i+len<q[head]) ++head;
						while (head<=tail&&f[q[tail]][j]+q[tail]<=f[i][j]+i) --tail;
						if (f[i][j]>=0) q[++tail]=i;
						if (head<=tail) dp[i][j]=max(dp[i][j],f[q[head]][j]+q[head]-i);
					}
				}
				break;
			}
			case 2:{
				for (rr int j=1;j<=m;++j){
				    head=1,tail=0;
					for (rr int i=1;i<=n;++i){
						if (!a[i][j]){
							head=1,tail=0;
						    continue;
						}
						while (head<=tail&&q[head]+len<i) ++head;
						while (head<=tail&&f[q[tail]][j]-q[tail]<=f[i][j]-i) --tail;
						if (f[i][j]>=0) q[++tail]=i;
						if (head<=tail) dp[i][j]=max(dp[i][j],f[q[head]][j]+i-q[head]);
					}
				}
				break;
			}
			case 3:{
				for (rr int i=1;i<=n;++i){
				    head=1,tail=0;
					for (rr int j=m;j>=1;--j){
						if (!a[i][j]){
							head=1,tail=0;
						    continue;
						}
						while (head<=tail&&j+len<q[head]) ++head;
						while (head<=tail&&f[i][q[tail]]+q[tail]<=f[i][j]+j) --tail;
						if (f[i][j]>=0) q[++tail]=j;
						if (head<=tail) dp[i][j]=max(dp[i][j],f[i][q[head]]+q[head]-j);
					}
				}
				break;
			}
			case 4:{
				for (rr int i=1;i<=n;++i){
				    head=1,tail=0;
					for (rr int j=1;j<=m;++j){
						if (!a[i][j]){
							head=1,tail=0;
						    continue;
						}
						while (head<=tail&&q[head]+len<j) ++head;
						while (head<=tail&&f[i][q[tail]]-q[tail]<=f[i][j]-j) --tail;
						if (f[i][j]>=0) q[++tail]=j;
						if (head<=tail) dp[i][j]=max(dp[i][j],f[i][q[head]]+j-q[head]);						
					}
				}
				break;
			}
		}
	}
	for (rr int i=1;i<=n;++i)
	for (rr int j=1;j<=m;++j)
	    ans=max(ans,dp[i][j]);
	return !printf("%d",ans);
}