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值，所以可以用滚动数组。

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

 //BZOJ 1047

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 inline int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,M=,INF=~0u>>;

 typedef long long LL;

 /******************tamplate*********************/

 int a,b,n,ans=INF;

 int mx[][N][M],mn[][N][M],v[N][N];

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("1047.in","r",stdin);

     freopen("1047.out","w",stdout);

 #endif

     a=getint(); b=getint(); n=getint();

     F(i,,a) F(j,,b) v[i][j]=getint();

     F(i,,a){

         int now=i&;

         F(j,,b){

             mx[now][j][]=mn[now][j][]=v[i][j];

             F(k,,min(n,min(i,j))){

                 mx[now][j][k]=max(v[i][j],max(v[i-k+][j-k+],max(mx[now][j-][k-],mx[now^][j][k-])));

                 mn[now][j][k]=min(v[i][j],min(v[i-k+][j-k+],min(mn[now][j-][k-],mn[now^][j][k-])));

             }

             if (min(i,j)>=n) ans=min(ans,mx[now][j][n]-mn[now][j][n]);

         }

     }

     printf("%d\n",ans);

     return ;

 }

（80分TLE）

　　看了下题解：单调队列！

　　豁然开朗，这不就是一个二维的滑动窗口吗？我个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$，更优）

 /**************************************************************

     Problem: 1047

     User: Tunix

     Language: C++

     Result: Accepted

     Time:1980 ms

     Memory:13240 kb

 ****************************************************************/

 //BZOJ 1047

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 inline int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,M=,INF=~0u>>;

 typedef long long LL;

 /******************tamplate*********************/

 int a,b,n,ans=INF;

 int mx[N][N],mn[N][N],Q[N],t1[N],t2[N],v[N][N];

 void get_row(){

     int l=,r=-;

     F(i,,a){

         l=,r=-;

         F(j,,b){

             while(l<=r && v[i][Q[r]]<=v[i][j])r--;

             Q[++r]=j;

             while(l<=r && j-Q[l]>=n) l++;

             if (j>=n) mx[i][j]=v[i][Q[l]];

         }

         l=,r=-;

         F(j,,b){

             while(l<=r && v[i][Q[r]]>=v[i][j])r--;

             Q[++r]=j;

             while(l<=r && j-Q[l]>=n) l++;

             if (j>=n) mn[i][j]=v[i][Q[l]];

         }

     }

 }

 void get_line(){

     int l,r;

     F(j,n,b){

         l=,r=-;

         F(i,,a){

             while(l<=r && mx[Q[r]][j]<=mx[i][j]) r--;

             Q[++r]=i;

             while(l<=r && i-Q[l]>=n) l++;

             if (i>=n) t1[i]=mx[Q[l]][j];

         }

         l=,r=-;

         F(i,,a){

             while(l<=r && mn[Q[r]][j]>=mn[i][j]) r--;

             Q[++r]=i;

             while(l<=r && i-Q[l]>=n) l++;

             if (i>=n) t2[i]=mn[Q[l]][j];

         }

         F(i,n,a) ans=min(ans,t1[i]-t2[i]);

     }

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("1047.in","r",stdin);

     freopen("1047.out","w",stdout);

 #endif

     a=getint(); b=getint(); n=getint();

     F(i,,a) F(j,,b) v[i][j]=getint();

     get_row();

     get_line();

     printf("%d\n",ans);

     return ;

 }

（正解）

巴特西

【BZOJ】【1047】【HAOI2007】理想的正方形

DP/单调队列优化

最新文章

热门文章