codeforces 573B B. Bear and Blocks(线段树+dp)
分类：
题目链接：
codeforces 573B
题目大意：
给出n个连续塔，每个塔有高度,每次取走最外层的块，问需要多少次操作能够拿光所有的块。
题目分析：首先我们可以知道第一次操作时，对于每个塔的变化满足如下的公式：
每次操作都满足如下的递推式，我们递推一下得到第k次操作第i的塔的高度：
因为k是常数，所以对于，每一项我们找到的就是最小的，这可用线段树进行维护。而且要设定两个虚拟的高度为0的塔，分别放在这一堆塔的两头，这样能够维护两侧的在每次操作拿光的情况。至于线段树维护的部分，就是遍历i两次，分别从小到大和从大到小，每次修改之前遍历过的位置为所要的状态，也就是之前遍历过的位置区间内全部加1，然后统计[0,i]的最小值，，右侧的同理。 AC代码：;int n;int l[MAX],r[MAX],h[MAX];struct Tree{int l,r,minn,lazy;}tree[MAX<<2];void push_up ( int u ){tree[u].minn = min ( tree[u<<1].minn , tree[u<<1|1].minn );}void build ( int u , int l , int r ){tree[u].l = l;tree[u].r = r;tree[u].lazy = 0;int mid = l+r>>1;if ( l == r ){tree[u].minn = h[l];return;}build ( u<<1 , l , mid );build ( u<<1|1 , mid+1 , r );push_up ( u );}void push_down ( int u ){int ll = tree[u].lazy;tree[u].lazy = 0;if ( ll ){tree[u<<1].lazy += ll;tree[u<<1|1].lazy += ll;tree[u<<1].minn += ll;tree[u<<1|1].minn += ll;}}void update ( int u , int left , int right ){int l = tree[u].l;int r = tree[u].r;int mid = l+r>>1;if ( left <= l && r <= right ){tree[u].minn += 1;tree[u].lazy += 1;return;}push_down ( u );if ( left <= mid && right >= l )update ( u<<1 , left , right );if ( left <= r && right > mid )update ( u<<1|1 , left , right );push_up ( u );}int query ( int u , int left , int right ){int l = tree[u].l;int r = tree[u].r;int mid = l+r>>1;if ( left <= l && r <= right )return tree[u].minn;push_down ( u );int ret = 1<<29;if ( left <= mid && right >= l )ret = min ( ret , query ( u<<1 , left , right ) );if ( left <= r && right > mid )ret = min ( ret , query ( u<<1|1 , left , right ) );return ret;}int main ( ){while ( ~scanf ( “%d” , &n ) ){h[0] = h[n+1] = 0;for ( int i = 1; i <= n ; i++ )scanf ( “%d” , &h[i] );build ( 1 , 0 , n+1 );for ( int i = 1 ; i <= n ; i++ ){update ( 1 , 0 , i-1 );l[i] = query ( 1 , 0 , i );}build ( 1 , 0 , n+1 );for ( int i = n ; i > 0 ; i– ){update ( 1 , i+1 , n+1 );r[i] = query ( 1 , i , n+1 );}int ans = 0;for ( int i = 1 ; i <= n ; i++ ){//cout << “YES : ” << l[i] << ” ” << r[i] << endl;ans = max ( ans , min ( l[i] , r[i] ));}printf ( “%d\n” , ans );}}
别想一下造出大海，必须先由小河川开始。
