Codeforces 1400E Clear the Multiset(贪心 + 分治)-白红宇

Codeforces 1400E Clear the Multiset(贪心 + 分治)

阅读量：391 次

发布时间：2019-03-05

本文共 1695 字，大约阅读时间需要 5 分钟。

在这里插入图片描述

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  // #define mid ((l + r) >> 1) #define Lson rt << 1, l , mid#define Rson rt << 1|1, mid + 1, r#define ms(a,al) memset(a,al,sizeof(a))#define log2(a) log(a)/log(2)#define _for(i,a,b) for( int i = (a); i < (b); ++i)#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 rep_(i,a,b) for( int i = (a); i > (b); -- i)#define lowbit(x) ((-x) & x)#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)#define INF 0x3f3f3f3f#define LLF 0x3f3f3f3f3f3f3f3f#define hash Hash#define next Next#define pb push_back#define f first#define s secondusing namespace std;const int N = 1e7 + 10, MOD = 1e9 + 7;const int maxn = 2e5;const long double eps = 1e-5;const int EPS = 500 * 500;typedef long long ll;typedef unsigned long long ull;typedef pair
                  
                    PII;typedef pair
                   
                     PLL;typedef pair
                    
                      PDD;template
                     
                       void read(T &x){ x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){ if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){ x = x*10+ch-48;ch=getchar();}x*=f;}template
                      
                        void read(T &first, Args& ... args) { read(first); read(args...);}int T, n;int a[N];inline int solve(int l, int r){ if(l > r) return 0; if(l == r) return (a[l] != 0); int maxv = 1e9 + 10; int mid; for(int i = l; i <= r; ++ i) if(a[i] < maxv){ maxv = a[i]; mid = i;} for(int i = l; i <= r; ++ i) a[i] -= maxv; return min(solve(l,mid - 1) + solve(mid + 1, r) + maxv,r - l + 1);}int main(){ int n; read(n); for(int i = 1; i <= n; ++ i) read(a[i]); printf("%d",solve(1,n)); return 0;}