DP/单调队列优化

---

　　一眼看上去就是DP

　　我想的naive的二维DP是酱紫滴：

　　　　mx[i][j][k]表示以(i,j)为右下角的k*k的正方形区域内的最大值，mn[i][j][k]同理

　　　　mx[i][j][k]=max(v[i][j],max(v[i-k+1][j-k+1],max(mx[i-1][j][k-1],mx[i][j-1][k-1])))，mn[i][j][k]同理

　　这个DP是既爆空间又爆时间的……我把空间优化了一下：由于转移的时候只用到了i-1行的DP值，所以可以用滚动数组。

　　但是时间上我优化不来了……

1 //BZOJ 1047 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define rep(i,n) for(int i=0;i
            
             =n;--i)11 #define pb push_back12 using namespace std;13 inline int getint(){14 int v=0,sign=1; char ch=getchar();15 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}16 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}17 return v*sign;18 }19 const int N=1010,M=110,INF=~0u>>2;20 typedef long long LL;21 /******************tamplate*********************/22 int a,b,n,ans=INF;23 int mx[2][N][M],mn[2][N][M],v[N][N];24 int main(){25 #ifndef ONLINE_JUDGE26 freopen("1047.in","r",stdin);27 freopen("1047.out","w",stdout);28 #endif29 a=getint(); b=getint(); n=getint();30 F(i,1,a) F(j,1,b) v[i][j]=getint();31 F(i,1,a){32 int now=i&1;33 F(j,1,b){34 mx[now][j][1]=mn[now][j][1]=v[i][j];35 F(k,2,min(n,min(i,j))){36 mx[now][j][k]=max(v[i][j],max(v[i-k+1][j-k+1],max(mx[now][j-1][k-1],mx[now^1][j][k-1])));37 mn[now][j][k]=min(v[i][j],min(v[i-k+1][j-k+1],min(mn[now][j-1][k-1],mn[now^1][j][k-1])));38 }39 if (min(i,j)>=n) ans=min(ans,mx[now][j][n]-mn[now][j][n]);40 }41 }42 printf("%d\n",ans);43 return 0;44 }
            
           
          
         
        
       
      

 

　　看了下题解：单调队列！

　　豁然开朗，这不就是一个二维的滑动窗口吗？我个sb没想到啊……

　　每行先做一遍单调队列优化DP，求出mx[i][j]表示以(i,j)为右端点的横着的n个格子的最大值（mn[i][j]同理）

　　然后再对每列做一遍……（这时候每一格的值就代表了横着的n个格子的最优值）

　　在对列进行DP的时候，为了节省(tou)空间(lan)我做完一列的DP就更新了一下答案……

P.S.感觉这个做法就是把一个二维的DP拆成(n+n)个一维DP分别搞……因为一维DP好搞、好优化= =所以总体上复杂度是降低了……（二维是n*n个状态，k的转移，一维是n个状态，转移可以优化到O(1)，所以虽然一维DP要做2n遍，但总复杂度是$2×n^2$，更优）

1 /************************************************************** 2     Problem: 1047 3     User: Tunix 4     Language: C++ 5     Result: Accepted 6     Time:1980 ms 7     Memory:13240 kb 8 ****************************************************************/ 9  10 //BZOJ 104711 #include
      
       12 #include
       
        13 #include
        
         14 #include
         
          15 #include
          
           16 #include
           
            17 #define rep(i,n) for(int i=0;i
            
             =n;--i)20 #define pb push_back21 using namespace std;22 inline int getint(){23 int v=0,sign=1; char ch=getchar();24 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}25 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}26 return v*sign;27 }28 const int N=1010,M=110,INF=~0u>>2;29 typedef long long LL;30 /******************tamplate*********************/31 int a,b,n,ans=INF;32 int mx[N][N],mn[N][N],Q[N],t1[N],t2[N],v[N][N];33 void get_row(){34 int l=0,r=-1;35 F(i,1,a){36 l=0,r=-1;37 F(j,1,b){38 while(l<=r && v[i][Q[r]]<=v[i][j])r--;39 Q[++r]=j;40 while(l<=r && j-Q[l]>=n) l++;41 if (j>=n) mx[i][j]=v[i][Q[l]];42 }43 l=0,r=-1;44 F(j,1,b){45 while(l<=r && v[i][Q[r]]>=v[i][j])r--;46 Q[++r]=j;47 while(l<=r && j-Q[l]>=n) l++;48 if (j>=n) mn[i][j]=v[i][Q[l]];49 }50 }51 }52 void get_line(){53 int l,r;54 F(j,n,b){55 l=0,r=-1;56 F(i,1,a){57 while(l<=r && mx[Q[r]][j]<=mx[i][j]) r--;58 Q[++r]=i;59 while(l<=r && i-Q[l]>=n) l++;60 if (i>=n) t1[i]=mx[Q[l]][j];61 }62 l=0,r=-1;63 F(i,1,a){64 while(l<=r && mn[Q[r]][j]>=mn[i][j]) r--;65 Q[++r]=i;66 while(l<=r && i-Q[l]>=n) l++;67 if (i>=n) t2[i]=mn[Q[l]][j];68 }69 F(i,n,a) ans=min(ans,t1[i]-t2[i]);70 }71 }72 int main(){73 #ifndef ONLINE_JUDGE74 freopen("1047.in","r",stdin);75 freopen("1047.out","w",stdout);76 #endif77 a=getint(); b=getint(); n=getint();78 F(i,1,a) F(j,1,b) v[i][j]=getint();79 get_row();80 get_line();81 printf("%d\n",ans);82 return 0;83 }