瑰丽华尔兹--单调队列

## 看到这道题，的标签 [我csdn的博客] (https://blog.csdn.net/qq_42421714/article/details/84963779) [我洛谷的博客](https://www.luogu.org/blog/cqj/gui-li-hua-er-zi-dan-diao-dui-lie) 说明啊，它可以用单调队列 易推出 ```cpp dp[x][y][t] = max(dp[x`][y`][t - 1] + 1,dp[x][y][t]); ``` 然后看一下数据范围？？？ n,m≤200，K≤200，T≤40000 `o(n^3)` 显然，TLE 然后老师讲了优化方案 T可以换成K 因为任一区间时间内，都只向一个方向走 。。。 然后就可以得到转移方程 ```cpp dp[x][y][k] = max(dp[x][y][k],dp[x1][ y1][k-1] + Abs(x - x1) + Abs(y - y2));` x1 y2 表示在x,y的前提下，dp[x1][y1][k - 1] + Abs(x - x1) + Abs(y - y2))的值最大（在范围内） 'o(n^3)' 等等，时间复杂度貌似没减 ``` 就是我们的单调队列神奇登场的时候了 ` 优化最内层循环` ## 思路 #### 滚动优化 ```cpp dp[x][y][k] 空间复杂度不小 可以发现 dp[x][y][k] 只跟上一次（dp[x][y][k - 1]）有关且满足x,y是单调递增或递减的 滚动优化一下 ``` #### 函数优化 ```cpp 4个方向 相信没有人会实诚de用4个if一一处理 ``` 所以我们用一个函数 传进去的 必须要有 限制·对应的哪种方向（用数组存一下向迷宫中的四个方向）·当前起点 #### 单调队列 单调队列中的元素不仅要看它自身的值，还要看。val + 它到当前点的距离（在移动范围内） 哪如何实现了 它到当前点的距离可以 ```cpp Abs(x - q[Index].x) + Abs(y - q[Index].y) ``` 放入队列时我是这样搞的 ```cpp while(tail >= head&&dp[x][y] > q[tail].val + M(tail)) tail--; ``` 但我们如何保证循环结束后取出来的就是最大值？（M()宏定义，详见code） 每个元素都是这样放进去的 那么假设队列q={1,2,3}(都是val值) 在枚举点时，每次距离都要加一 1 + 1 = 2 2 + 1 = 3 3 + 1 = 4 q = {1,2,3} 顺序没有**发生改变** #### 注意 由于滚动优化后了，处理一个点时只能先放入单调队列 再取出当前最大值 还有`X`，是不能走的，遇到就重新清一下队列（把Head = 1,tail = 0） ## code ```cpp #include <cstdio> #include <cstring> #define M(Index) Abs(x - q[Index].x) + Abs(y - q[Index].y) using namespace std; const int MAXN = 202; bool Map[MAXN][MAXN]; int n,m,dp[MAXN][MAXN],ans; int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; class T { public: int val; int x,y; }; template<typename TT> inline TT Max(TT a,TT b) {if(a > b) return a;return b;} template<typename TT> inline TT Abs(TT a) {if(a < 0) return -a;return a;} inline void Dp(int x,int y,int con,int s) { s--; T q[MAXN]; int head = 1,tail = 0; for(;x <= n&&x > 0&&y <= m&&y > 0;x += dir[s][0],y += dir[s][1]) if(Map[x][y] == 0) head = 1,tail = 0; else { while(tail >= head&&dp[x][y] > q[tail].val + M(tail)) tail--; tail++; q[tail].val = dp[x][y]; q[tail].x = x; q[tail].y = y; while(head <= tail&&(Abs(x - q[head].x) > con||Abs(y - q[head].y) > con)) head++; dp[x][y] = Max(dp[x][y],q[head].val + M(head)); ans = Max(ans,dp[x][y]); } } int main() { int x,y,k,i,j; scanf("%d%d%d%d%d",&n,&m,&x,&y,&k); char a; for(i = 1;i <= n;i++) { getchar(); for(j = 1;j <= m;j++) { scanf("%c",&a); if(a == '.') Map[i][j] = 1; } } memset(dp,-0x7f7f7f,sizeof(dp)); dp[x][y] = 0; for(i = 1;i <= k;i++) { int s,t,d,con; scanf("%d%d%d",&s,&t,&d); con = t - s + 1; if(d == 1) for(j = 1;j <= m;j++) Dp(n,j,con,1); if(d == 2) for(j = 1;j <= m;j++) Dp(1,j,con,2); if(d == 3) for(j = 1;j <= n;j++) Dp(j,m,con,3); if(d == 4) for(j = 1;j <= n;j++) Dp(j,1,con,4); } printf("%d",ans); return 0; } ```