https://www.luogu.com.cn/problem/P2254
给你一张地图，一些地方不能走，输入初始位置，(K)段时间，每段时间内要么只能往指定的方向走，要么不走，问最远能走多长的路径。(n,m,kleq 200)
用(f[i][j][k])表示第(k)段时间走完之后在((i,j))处的答案，暴力转移(egin{aligned}f[i][j][k]=max_{t=0}^{ed_k-st_k+1}{f[i-tDelta x][j-tDelta y][k-1]+t}end{aligned})，这样就得到了一个四次方的DP，但是应该是数据太水（以及可能因为是十几年前的题了，当时测评机没这么快）…这么个大暴力就过了这题：
rep(k,1,K)rep(i,1,n)rep(j,1,m)if(avl[i][j]){
int mx=-INF;
rep(t,0,ed[k]-st[k]+1){
int cx=i-t*di[d[k]],cy=j-t*dj[d[k]];
if(!check(cx,cy))break;
if(f[cx][cy][k-1]==-INF)continue;
mx=max(mx,f[cx][cy][k-1]+t);
}
f[i][j][k]=mx;
}
不过还是来优化转移过程，其实(Delta x,Delta y)里面会有一个是0，假设(j)定下来，(i)是这次动的方向，我们对于每个确定的(k,j)，其实可以(O(n))对
(f[i][j][k]=max_{t=0}^{len}{f[i-tDelta x][j][k-1]+t})进行转移：假设这个(d[k])意味着(i)只能增大，那我就从1枚举(i)，用单调队列维护(f[i-tDelta x][j][k-1]-t)，每次再用(Q.front()+t)来更新答案（注意前面单调队列里维护的是(-t)，因为原来dp式子里的(t)的含义其实是两个位置的距离，相当于是(t_{当前}-t_{从哪转移来})）
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
typedef vector<int> vi;
const int N=205;
const int INF=(~0u>>2);
struct Queue
{
int x[N],y[N],s[N],st,ed;
void clear(){st=1;ed=0;}
void push_back(int a,int b,int v){ed++;x[ed]=a;y[ed]=b;s[ed]=v;}
void pop_back(){ed--;}
void pop_front(){st++;}
bool empty(){return st>ed;}
}Q;
int n,m,K,t,sx,sy;
int st[N],ed[N],d[N],f[N][N][N];
int di[]={0,-1,1,0,0},dj[]={0,0,0,-1,1};
bool avl[N][N];
char str[N];
bool inside(int x,int y){return (1<=x&&x<=n&&1<=y&&y<=m);}
bool check(int x,int y){return (avl[x][y]&&inside(x,y));}
bool in_range(int x1,int y1,int x2,int y2,int d)
{
return (abs(x1-x2)<=d&&abs(y1-y2)<=d);
}
void solve(int x,int y,int len,int d,int k)
{
int t=0;Q.clear();
while(inside(x,y))
{
if(check(x,y))
{
while(!Q.empty())
{
int qx=Q.x[Q.st],qy=Q.y[Q.st];
if(in_range(qx,qy,x,y,len))break;
else Q.pop_front();
}
while(!Q.empty()&&Q.s[Q.ed]<=f[x][y][k-1]-t)
Q.pop_back();
if(f[x][y][k-1]!=-INF)
Q.push_back(x,y,f[x][y][k-1]-t);
if(!Q.empty())f[x][y][k]=Q.s[Q.st]+t;
}else
{
while(!Q.empty())Q.pop_front();
}
t++;
x+=di[d];y+=dj[d];
}
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&K);
rep(i,1,n)
{
scanf("%s",str+1);
rep(j,1,m)if(str[j]=='.')avl[i][j]=1;
}
rep(i,1,K)scanf("%d%d%d",&st[i],&ed[i],&d[i]);
rep(i,1,n)rep(j,1,m)rep(k,0,K)f[i][j][k]=-INF;
f[sx][sy][0]=0;
rep(k,1,K)
{
int len=ed[k]-st[k]+1;
if(d[k]==1)rep(j,1,m)solve(n,j,len,d[k],k);
if(d[k]==2)rep(j,1,m)solve(1,j,len,d[k],k);
if(d[k]==3)rep(i,1,n)solve(i,m,len,d[k],k);
if(d[k]==4)rep(i,1,n)solve(i,1,len,d[k],k);
}
int ret=-INF;
rep(i,1,n)rep(j,1,m)if(avl[i][j])ret=max(ret,f[i][j][K]);
printf("%d",ret);
return 0;
}