fork download
copy 
  1. program mountain;
  2. Uses sysutils, Math;
  3.  
  4. const
  5.     MAXN = 100005;
  6.  
  7. Type elenco= Array of LongInt;
  8.  
  9. var
  10.     ANS, N, i, id, x, maxMountainLength, lung, len, count : LongInt;
  11.     P, leftLIS, rightLIS, valli: Array[0..MAXN-1] of LongInt;
  12.     LIS : elenco;
  13.     rimossi : Ansistring;
  14.  
  15.  
  16.  
  17. Procedure ricercaUpper (var w:elenco; target:Longint); (*ritorna indice del valore maggiore/uguale a target oppure -1 se non esiste*)
  18.   var m,start,eend: Longint;
  19.  
  20.  begin  
  21.    start:=0; eend:=len-1 ; m:=-1;
  22.    while start<=eend do
  23.            begin
  24.                   m:=(start + eend) div 2;
  25.                   if w[m]<target then  start:=m+1
  26.                                  else  if w[m]>=target then  begin id:=m;  eend:=m-1 end;
  27.            end;
  28.    if start=len then id:=-1;
  29.  
  30.  end;
  31.  
  32.  
  33.  
  34.  
  35. begin
  36.     (*assign(input,  'input.txt');  reset(input);
  37.     assign(output, 'output.txt'); rewrite(output);*)  
  38.  
  39.     ReadLn(N);
  40.     rimossi:=''; lung:=N;  
  41.     for i:=0 to N-1 do begin
  42.                         Read(P[i]);
  43.                         rimossi:=rimossi+IntTostr(P[i]);
  44.                         valli[i]:=0; 
  45.                        end;  
  46.     ReadLn();
  47.      count:=0;
  48.      i:=2; 
  49.      while i<lung do
  50.               begin
  51.                 if  (rimossi[i]<rimossi[i-1]) and (rimossi[i]<rimossi[i+1])                    
  52.                                       then
  53.                                            begin
  54.                                                 if (i+count)<=lung then valli[i+count-1]:=-1;
  55.                                                 delete(rimossi,i,1);
  56.                                                 lung:=lung-1;  count:=count+1;
  57.                                                 setLength(rimossi,lung); 
  58.                                            end
  59.                                        else i:=i+1;
  60.               end; 
  61.  
  62.     ANS := 0; 
  63. 	(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  64. 	(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  65.     len:=1; SetLength(LIS,len); LIS[0]:=P[0];
  66.     for i:=0 to  N-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; end;
  67.     (*Calculate LIS from left to right for each position*)
  68.     for i :=1 to N-1 do
  69.                     begin
  70.                         ricercaUpper(Lis, P[i]);
  71.                        // if element in not present in lis insert at the end
  72.  
  73.                         if id=-1 then
  74.                                    begin
  75.                                      len:=len+1;
  76.                                      SetLength(LIS,len);
  77.                                      LIS[len-1] := P[i];
  78.                                      leftLIS[i]:=len;
  79.                                    end
  80.                                  else
  81.                                     begin
  82.                                       // if element is to be inserted in lis
  83.                                       if (id<>0) and (valli[id]=-1) then
  84.                                                      begin
  85.                                                         LIS[id] := P[i];
  86.                                                         leftLIS[i]:=id+1;                                                       
  87.                                                      end
  88.                                                else 
  89.                                                 leftLIS[i]:=0;
  90.  
  91.                                     end;                    
  92.                     end; 
  93.  
  94.        (* Calculate LIS from right to left (decreasing subsequence) for each position*)
  95.    rimossi:='';
  96.    for i:=N-1 downto 0 do 
  97.                        begin
  98.                         rimossi:=rimossi+IntTostr(P[i]);
  99.                         valli[i]:=0; 
  100.                        end;
  101.  
  102.     count:=0; lung:=N;
  103.      i:=2; 
  104.      while i<lung do
  105.               begin
  106.                 if  (rimossi[i]<rimossi[i-1]) and (rimossi[i]<rimossi[i+1])                    
  107.                                       then
  108.                                            begin
  109.                                                 if (i+count)<=lung then valli[i+count-1]:=-1;
  110.                                                 delete(rimossi,i,1);
  111.                                                 lung:=lung-1;  count:=count+1;
  112.                                                 setLength(rimossi,lung); 
  113.                                            end
  114.                                        else i:=i+1;
  115.               end;                    
  116.    len:=1; SetLength(LIS,len); LIS[0]:=P[N-1]; 
  117.  
  118.    for i :=N-2 downto 0 do
  119.                     begin
  120.                         ricercaUpper(Lis, P[i]);
  121.                         if id=-1 then
  122.                                    begin
  123.                                      len:=len+1;
  124.                                      SetLength(LIS,len);
  125.                                      LIS[len-1] := P[i];
  126.                                      rightLIS[i]:=len;
  127.                                    end
  128.                                  else
  129.                                     begin
  130.                                       // if element is to be inserted in lis
  131.                                       if (id<>0) and (valli[id]=-1) then
  132.                                                      begin
  133.                                                         LIS[id] := P[i];
  134.                                                         rightLIS[i]:=id+1;                                                        
  135.                                                      end
  136.                                                 else  
  137.                                                    rightLIS[i]:=0;
  138.  
  139.  
  140.                                    end;                    
  141.                     end;
  142.  
  143.     maxMountainLength := 0;
  144.     (* Find the maximum length of mountain subsequence*)
  145.     // for every index check for longest mountain array,
  146.     for i := 0 to N-1 do
  147.              begin
  148.                 if (leftLIS[i] >=1) AND (rightLIS[i] >= 1) then 
  149.                       begin
  150.                         x := leftLIS[i] + rightLIS[i] - 1;
  151.                         maxMountainLength := max(maxMountainLength, x);
  152.                       end;  
  153.              end;
  154.     // returning removals
  155.  
  156.    ANS:= N - maxMountainLength; 
  157.    WriteLn(ANS);
  158. end.
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
7 
1 4 0 2 3 6 5
stdout
copy 
3
https://ideone.com/Ena6YF
language:
Pascal (fpc 3.0.4)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!