本文主要是介绍【codeforces】480E Parking Lot 线段树+DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【codeforces】480E Parking Lot
题目分析：很早以前在同学助攻下写出来的，想想还是放出来好了，是个不错的思想。
原题是在动态将可行区域变成不可行区域的同时求全局最大子正方形，n，m，k至多2000。
既然只有加点，于是我们离线，倒着来，这样便只有删点。
我们给每个节点（i,j）保存它向上能延伸的距离U[i][j]以及向下能延伸的距离D[i][j]。
易知删除一个点最多影响一列上的U和D，暴力更新U，D。复杂度为O（n^2），可以承受。
首先我们预处理出所有点都加上后的最大子正方形（直接dp）。
然后建立一棵线段树，线段树保存一段区间向下延伸的最大子矩形的高度（即最小的D），同时保存一段区间向上延伸的最大子矩形的高度（即最小的U）。
每次删点时我们暴力维护U，D，然后对删点的那一行建立线段树进行最大子正方形大小的维护（最大子正方形大小的改变一定和这一行上的点有关）。
维护方法直接见代码好了。
然后查询就是O（1）的操作了。
觉得这解题的思想很不错，值得思考~
而且这题的解法貌似很多的样子。。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , mconst int MAXN = 2005 ;
const int INF = 0x3f3f3f3f ;struct Node {int x , y ;
} p[MAXN] ;int minu[MAXN << 2] , mind[MAXN << 2] ;
int G[MAXN][MAXN] ;
int U[MAXN][MAXN] ;
int D[MAXN][MAXN] ;
int left[MAXN] , right[MAXN] ;
int ans[MAXN] ;
int n , m , k ;int min1 , min2 ;
void query ( int L , int R , int o , int l , int r ) {if ( L <= l && r <= R ) {min1 = min ( min1 , minu[o] ) ;min2 = min ( min2 , mind[o] ) ;return ;}int m = mid ;if ( L <= m ) query ( L , R , lson ) ;if ( m < R ) query ( L , R , rson ) ;
}void build ( int x , int o , int l , int r ) {if ( l == r ) {minu[o] = U[x][l] ;mind[o] = D[x][l] ;return ;}int m = mid ;build ( x , lson ) ;build ( x , rson ) ;minu[o] = min ( minu[ls] , minu[rs] ) ;mind[o] = min ( mind[ls] , mind[rs] ) ;
}int calc () {int ans = 0 ;For ( i , 1 , n ) {For ( j , 1 , m ) {int x = j ;while ( x > 1 && U[i][x - 1] >= U[i][j] ) x = left[x - 1] ;left[j] = x ;}rev ( j , m , 1 ) {int x = j ;while ( x < m && U[i][x + 1] >= U[i][j] ) x = right[x + 1] ;right[j] = x ;}For ( j , 1 , m ) {ans = max ( ans , min ( U[i][j] , right[j] - left[j] + 1 ) ) ;//printf ( "%d %d %d\n" , U[i][j] , left[j] , right[j] ) ;}//printf ( "%d\n" , ans ) ;}return ans ;
}int check ( int size , int y ) {if ( size > n || size > m ) return 0 ;For ( i , max ( 1 , y - size + 1 ) , m - size + 1 ) {min1 = min2 = INF ;query ( i , i + size - 1 , root ) ;if ( min1 + min2 - 1 >= size ) return 1 ;}return 0 ;
}void solve () {clr ( U , 0 ) ;clr ( D , 0 ) ;clr ( G , 0 ) ;clr ( ans , 0 ) ;For ( i , 1 , n ) {getchar () ;For ( j , 1 , m ) {char c = getchar () ;G[i][j] = c == '.' ;}}rep ( i , 0 , k ) {scanf ( "%d%d" , &p[i].x , &p[i].y ) ;G[p[i].x][p[i].y] = 0 ;}//For ( i , 1 , n ) For ( j , 1 , m ) printf ( "%d%c" , G[i][j] , j < m ? ' ' : '\n' ) ;For ( i , 1 , n ) For ( j , 1 , m ) U[i][j] = G[i][j] ? U[i - 1][j] + 1 : 0 ;rev ( i , n , 1 ) For ( j , 1 , m ) D[i][j] = G[i][j] ? D[i + 1][j] + 1 : 0 ;int size = calc () ;rev ( i , k - 1 , 0 ) {ans[i] = size ;if ( !i ) break ;int x = p[i].x ;int y = p[i].y ;G[x][y] = 1 ;U[x][y] = U[x - 1][y] + 1 ;For ( j , x + 1 , n ) {if ( !G[j][y] ) break ;U[j][y] += U[x][y] ;}D[x][y] = D[x + 1][y] + 1 ;rev ( j , x - 1 , 1 ) {if ( !G[j][y] ) break ;D[j][y] += D[x][y] ;}build ( x , root ) ;while ( check ( size + 1 , y ) ) ++ size ;}rep ( i , 0 , k ) printf ( "%d\n" , ans[i] ) ;
}int main () {while ( ~scanf ( "%d%d%d" , &n , &m , &k ) ) solve () ;return 0 ;
}
这篇关于【codeforces】480E Parking Lot 线段树+DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
