看了一篇题解!来练习单调队列优化的DP

用单调队列分别维护行与列

在维护的同事随便维护最大值和最小值

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define maxn 1010 using namespace std ; int n , m , k , front , Front , back ,Back , ans ; int a[maxn][maxn] ,q[maxn] , Q[maxn] ; int x[maxn][maxn] , X[maxn][maxn] ; int y[maxn][maxn] , Y[maxn][maxn] ; int main () { cin >> n >> m >> k ; for(int i = 1 ; i <= n ; i ++) { for(int j = 1 ; j <= m ; j ++) { cin >> a[i][j] ; } } for(int i = 1 ; i <= n ; i ++) { Front = Back = front = back = Q[1] = q[1] = 1 ; for(int j = 2 ; j <= m ; j ++) { while(a[i][j] >= a[i][Q[Back]] && Front <= Back) Back -- ; while(a[i][j] <= a[i][q[back]] && front <= back) back -- ; Back ++ ;back ++ ; Q[Back] = j ;q[back] = j ; while(j-Q[Front] >= k) Front ++ ; while(j-q[front] >= k) front ++ ; if(j >= k) X[i][j-k+1] = a[i][Q[Front]] , x[i][j-k+1] = a[i][q[front]] ; } } /*for(int i = 1 ; i <= m-k+1 ; i ++) { Front = Back = front = back = Q[1] = q[1] = 1 ; for(int j = 2 ; j <= n ; j ++) { while(X[j][i] >= X[Q[Back]][i] && Front <= Back) Back -- ; while(x[j][i] <= x[q[back]][i] && front <= back) back -- ; Back ++ , back ++ ; Q[Back] = j , q[back] = j ; while(j-Q[Front] >= k) Front ++ ; while(j-q[front] >= k) front ++ ; if(j >= k) Y[j-k+1][i] = X[Q[Front]][i] , y[i-k+1][i] = x[q[front]][i] ; } }*/ for (int I=1;I<=m-k+1;I++) { Front=Back=front=back=Q[1]=q[1]=1; for (int i=2;i<=n;i++) { while (X[i][I]>=X[Q[Back]][I]&&Front<=Back) Back--; while (x[i][I]<=x[q[back]][I]&&front<=back) back--; Back++;back++;Q[Back]=i;q[back]=i; while (i-Q[Front]>=k) Front++; while (i-q[front]>=k) front++; if (i>=k) Y[i-k+1][I]=X[Q[Front]][I],y[i-k+1][I]=x[q[front]][I]; } } ans = 0x3f3f3f3f ; for(int i = 1 ; i <= n-k+1 ; i ++) { for(int j = 1 ; j <= m-k+1 ; j ++) { ans = min(ans,Y[i][j]-y[i][j]) ; } } printf("%d\n",ans); return 0 ; }