做4次单调队列优化DP。

 

1 /************************************************************** 2     Problem: 1047 3     User: idy002 4     Language: C++ 5     Result: Accepted 6     Time:2088 ms 7     Memory:16756 kb 8 ****************************************************************/ 9  10 #include 
      
       11 #define N 101012  13 struct Pair {14     int i, j, v;15     Pair(){}16     Pair( int i, int j, int v ):i(i),j(j),v(v){}17 };18  19 int n, m, r, ans;20 int v[N][N], dp[N][N], dmin[N][N], dmax[N][N];21 Pair qu[N]; int bg, ed;22  23 int dodp() {24     //  min25     for( int i=1; i<=n; i++ ) {26         bg=1, ed=0;27         for( int j=1; j<=m; j++ ) {28             while( bg<=ed && qu[bg].j
       
        v[i][j] ) ed--;30             qu[++ed] = Pair(i,j,v[i][j]);31             dp[i][j] = qu[bg].v;32         }33     }34     for( int j=1; j<=m; j++ ) {35         bg=1, ed=0;36         for( int i=1; i<=n; i++ ) {37             while( bg<=ed && qu[bg].i
        
         dp[i][j] ) ed--;39             qu[++ed] = Pair(i,j,dp[i][j]);40             dmin[i][j] = qu[bg].v;41         }42     }43     //  max44     for( int i=1; i<=n; i++ ) {45         bg=1, ed=0;46         for( int j=1; j<=m; j++ ) {47             while( bg<=ed && qu[bg].j
         
          tans ) ans=tans;67         }68     /*  debug69     fprintf( stderr, "n=%d m=%d r=%d\n", n, m, r );70     fprintf( stderr, "v:\n" );71     for( int i=1; i<=n; i++ ) {72         for( int j=1; j<=m; j++ )73             fprintf( stderr, "%2d ", v[i][j] );74         fprintf( stderr, "\n" );75     }76     fprintf( stderr, "dmin:\n" );77     for( int i=1; i<=n; i++ ) {78         for( int j=1; j<=m; j++ ) 79             fprintf( stderr, "%2d ", dmin[i][j] );80         fprintf( stderr, "\n" );81     }82     fprintf( stderr, "dmax:\n" );83     for( int i=1; i<=n; i++ ) {84         for( int j=1; j<=m; j++ )85             fprintf( stderr, "%2d ", dmax[i][j] );86         fprintf( stderr, "\n" );87     }88     */89     return ans;90 }91 int main() {92     scanf( "%d%d%d", &n, &m, &r );93     for( int i=1; i<=n; i++ )94         for( int j=1; j<=m; j++ )95             scanf( "%d", &v[i][j] );96     printf( "%d\n", dodp() );97 }