Codeforces 488D Strip (set+DP)
Alexandra has a paper strip withnnumbers on it. Let's call themaifrom left to right.
Now Alexandra wants to split it into some pieces (possibly1). For each piece of strip, it must satisfy:
Please help Alexandra to find the minimal number of pieces meeting the condition above.
The first line contains three space-separated integersn, s, l(1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).
The second line containsnintegersaiseparated by spaces ( - 109 ≤ ai ≤ 109).
Output the minimal number of strip pieces.
If there are no ways to split the strip, output -1.
7 2 2
1 3 1 2 4 1 2
3
7 2 2
1 100 1 100 1 100 1
-1
For the first sample, we can split the strip into3pieces:[1, 3, 1], [2, 4], [1, 2].
For the second sample, we can't let1and100be on the same piece, so no solution exists.
题意是给出一个长度为n的序列,问最少能够分割多少分。
使得,每一分的长度大于等于l,最大值与最少值的差值最大为s 。
我的方法是3颗线段树,2颗维护最大最小值, 1棵维护 dp[i-1]+1 最小的位置。
然后二分出尽量左的位置使得最大最小值差值最大不超过s ,
然后从这个位置到当前位置取出dp[i-1]+1 最小的位置。然后再更新。
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <vector> #include <queue> #include <map> #include <set> #include <stack> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; const int inf = 1e9+7; const double PI = acos(-1.0); const double eps = 1e-6 ; #define root 1,n,1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define lr rt<<1 #define rr rt<<1|1 int n , m , dif , e[N] , dp[N]; int d_M[N<<2] , d_m[N<<2] , p_m[N<<2]; void Up( int rt ) { d_M[rt] = max( d_M[lr] , d_M[rr] ); d_m[rt] = min( d_m[lr] , d_m[rr] ); } void Up2( int rt ) { if( dp[ p_m[lr] - 1 ] + 1 < dp[ p_m[rr] - 1 ] + 1 ) p_m[rt] = p_m[lr] ; else p_m[rt] = p_m[rr] ; } void build( int l , int r , int rt ){ if( l == r ) { p_m[rt] = l ; d_M[rt] = d_m[rt] = e[l] ; return ; } int mid = (l+r)>>1; build(lson) , build(rson) ; Up(rt); Up2(rt); } int temp_M , temp_m , temp_dpm; void update( int l , int r , int rt , int x , int val ) { if( l == r ) { dp[ x ] = val ; return ; } int mid = (l+r)>>1 ; if( x <= mid ) update( lson , x , val ); else update(rson,x,val); Up2(rt); } int get_min_pos( int l , int r , int rt , int L , int R ){ if( l == L && r == R ) { return p_m[rt]; } int mid = (l+r) >> 1 ; if( R <= mid ) return get_min_pos( lson , L ,R ) ; else if( L > mid ) return get_min_pos( rson ,L ,R ) ; else { int temp_l = get_min_pos( lson , L , mid ) , temp_r = get_min_pos( rson , mid+1 , R ); if( dp[ temp_l - 1 ] + 1 < dp[ temp_r - 1 ] + 1 ) return temp_l; else return temp_r; } } void query( int l , int r , int rt , int L , int R ) { if( l == L && r == R ) { temp_M = max( temp_M , d_M[rt] ) ; temp_m = min( temp_m , d_m[rt] ); return ; } int mid = ( l+r ) >>1; if( R <= mid ) query(lson,L,R); else if( L > mid )query(rson,L,R); else query(lson,L,mid) , query(rson,mid+1,R); } void init() { for( int i = 1 ; i <= n ; ++i ) dp[i] = inf ; } void clr() { temp_m = inf , temp_M = -inf; temp_dpm = inf ; } int find( int l , int r ){ int pos = -1 , goal = r ; while( l <= r ) { int mid = (l+r)>>1; clr(),query(root,mid,goal); if( abs( temp_M - temp_m ) <= dif ) pos = mid , r = mid - 1; else l = mid + 1; } return pos; } void test() { for( int i = 0 ; i <= n ; ++i ) cout << dp[i] << ' ' ;cout << endl ; } void run () { for( int i = 1 ; i <= n ; ++i ) cin >> e[i] ; init(),build(root); for( int i = 1 ; i <= n ; ++i ) { int pos = find( 1 , i ) ; if( pos == -1 || i - pos + 1 < m ) continue ; if( pos - 1 == i - m ) { update( root , i , dp[ pos - 1 ] + 1 ) ; continue ; } pos = get_min_pos( root , pos , i - m ); update( root , i , dp[ pos - 1 ] + 1 ) ; } if( dp[n] < inf )cout << dp[n] << endl ; else cout << "-1" << endl ; } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL ios::sync_with_stdio(false); while( cin >> n >> dif >> m )run() ; }View Code
之前一直不会set...
在cf上看别人的代码,被完爆码量。
#include <bits/stdc++.h> #define X first #define Y second #define INF 1000000009 using namespace std; typedef pair<int,int> pii; int n, s, l, a[100005]; int dp[100005]; set <pii> S, R; int main(){ scanf("%d %d %d", &n, &s, &l); for(int i = 1; i <= n; i ++) scanf("%d", &a[i]); memset(dp, 0, sizeof dp); int j = 1; for(int i = 1; i <= n; i ++){ S.insert(pii(a[i], i)); while(!S.empty() && S.rbegin()->X - S.begin()->X > s){ S.erase(pii(a[j], j)); j ++; } if(i >= l && dp[i - l] != -1) R.insert(pii(dp[i - l], i - l)); while(!R.empty() && R.begin()->Y < j - 1) R.erase(R.begin()); if(R.empty()) dp[i] = -1; else dp[i] = R.begin()->X + 1; } printf("%d\n", dp[n]); return 0; }View Code 优质内容筛选与推荐>>