做题记录整理dp810 P2254 [NOI2005] 瑰丽华尔兹（2022/9/23）

P2254 [NOI2005] 瑰丽华尔兹
题解
这题的难点在与dp的递推方程的书写
如果写对了递推方程，想到单调队列优化是很自然的（然而我想到了不会打）
还有递推方程的具体代码实现也挺难的（似乎直接记忆化搜索比较简单）

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
struct node{
    int dp, pos;
}q[505]; 
int n,m,sx,sy,kk,ans,dp[505][505];
int dx[5] = {0,-1,1,0,0};
int dy[5] = {0,0,0,-1,1}; 
char ma[505][505];
void cl(int x,int y,int len,int d) 
{
	int hd = 1, tl = 0;
	for(int i = 1;;i++)
	{
		if(!(x>=1&&x<=n&&y>=1&&y<=m)) break;
		if(ma[x][y]=='x') hd=1,tl=0;
		else
		{
			while(hd<=tl&&q[tl].dp+i-q[tl].pos<dp[x][y]) tl--;
			q[++tl]=node{dp[x][y],i};
			
			
			if(q[tl].pos-q[hd].pos>len) hd++;
			dp[x][y]=q[hd].dp+i-q[hd].pos; 
			
			
			ans=max(ans,dp[x][y]);
		}
	    x+=dx[d],y+=dy[d];
	}	
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&kk);
	for1(i,1,n)
	 scanf("%s",ma[i]+1);
	memset(dp,0xf3,sizeof(dp));
	dp[sx][sy]=0;
	int s,t,d,len;
	for1(k,1,kk)
	{
		scanf("%d%d%d",&s,&t,&d);
		len=t-s+1;
		if(d==1) 
		    for1(i,1,m) 
			    cl(n,i,len,d);
		if(d==2) 
		    for1(i,1,m) 
			    cl(1,i,len,d);
		if(d==3) 
		    for1(i,1,n) 
			    cl(i,m,len,d);
		if(d==4) 
		    for1(i,1,n) 
			    cl(i,1,len,d);
	}
	printf("%d", ans);
	return 0;
}