开始之前先致敬一下伟大的海上钢琴师1900.
我们想到可以对于每一个时间段进行DP，这样的话，用dp[i][j][t]表示在第t个时间段的结束，钢琴在第（i，j）位置的时候最远行走的路程。对于不同的方向转移不大一样，有dp[i][j][t] = max{dp[p][q][t-1] + i - p + j - q},其中（p，q）是上一次钢琴的位置。p，q的范围可以自行进行确定。（至于为什么可以这样转移，因为小天使帮忙固定了，就相当于是你转移的范围变小了）
所以说其实这个也是可以转化为单调队列优化DP的，dp[i][j][t]可以说是由前一段区间（也就是钢琴能滑到的范围转移过来的），直接用单调队列优化一下就可以了。
这道题需要分类讨论四个方向，注意从四个方向的起始点是不同的，然后其他的操作就没什么特殊的啦。由于单调队列可以自动为我们保存在t-1时间段的情况，所以其实t那一维不需要开，直接转化成二维DP。
还有很重要的一点，因为道路上存在箱子，箱子隔开的两段路是不能转移的，所以在DP过程中如果遇到箱子的话，立即清空单调队列，继续DP即可。一开始因为其他地点是不合法情况，要初始化为-INF，只有开始点是0.
看一下代码。
// luogu-judger-enable-o2#include#include #include #include #include #include #include #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')using namespace std;typedef long long ll;const int M = 10005;const int INF = 1000000009;int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op;}struct line{ int l,r,dir;}a[205];struct node{ int val,pos;}q[205];int n,m,sx,sy,k,dp[205][205],g[205][205],head,tail,ans;int dx[5] = { 0,-1,1,0,0},dy[5] = { 0,0,0,-1,1};char s[205];void solve(int x,int y,int len,int dir,int t){ head = 1,tail = 0; int cnt = 0; while(++cnt) { if(x < 1 || x > n || y < 1 || y > m) break; if(g[x][y]) head = 1,tail = 0; else { while(head <= tail && q[tail].val + cnt - q[tail].pos <= dp[x][y]) tail--; q[++tail].val = dp[x][y],q[tail].pos = cnt; while(head <= tail && q[head].pos < cnt - len) head++; dp[x][y] = max(dp[x][y],q[head].val + cnt - q[head].pos); } x += dx[dir],y += dy[dir]; }}int main(){ n = read(),m = read(),sx = read(),sy = read(),k = read(); rep(i,1,n) { scanf("%s",s+1); rep(j,1,m) if(s[j] == 'x') g[i][j] = 1; } rep(i,1,k) a[i].l = read(),a[i].r = read(),a[i].dir = read(); memset(dp,-0x3f,sizeof(dp)); dp[sx][sy] = 0; rep(p,1,k) { int len = a[p].r - a[p].l + 1; if(a[p].dir == 1) rep(i,1,m) solve(n,i,len,a[p].dir,p); if(a[p].dir == 2) rep(i,1,m) solve(1,i,len,a[p].dir,p); if(a[p].dir == 3) rep(i,1,n) solve(i,m,len,a[p].dir,p); if(a[p].dir == 4) rep(i,1,n) solve(i,1,len,a[p].dir,p); } rep(i,1,n) rep(j,1,m) ans = max(ans,dp[i][j]); printf("%d\n",ans); return 0;}