fork download
copy 
  1. program mountain;
  2. Uses sysutils, Math;
  3.  
  4. const
  5.     MAXN = 100005;
  6.  
  7. var
  8.     ANS, N, i, j,h,w, maxMountainLength, lung : LongInt;
  9.     P, leftLIS, rightLIS  : Array[0..MAXN-1] of LongInt;
  10.     rimossi : Ansistring;
  11.     rimosso: boolean;
  12. begin
  13.     (*assign(input,  'input.txt');  reset(input);
  14.     assign(output, 'output.txt'); rewrite(output);*)  
  15.  
  16.     ReadLn(N);
  17.     rimossi:=''; lung:=N;
  18.     for i:=0 to N-1 do begin
  19.                         Read(P[i]);
  20.                         rimossi:=rimossi+IntTostr(P[i]);
  21.                        end;  
  22.     ReadLn();
  23.     rimosso:=false; w:=2; h:=1;
  24.     while h<5 do 
  25.        begin
  26.         w:=2; rimosso:=false;
  27.         while w<lung do
  28.               begin
  29.                 if  (rimossi[w]<rimossi[w-1]) and (rimossi[w]<rimossi[w+1]) then
  30.                                                                               begin
  31.                                                                                 delete(rimossi,w,1);
  32.                                                                                 lung:=lung-1;
  33.                                                                                 rimosso:=true;
  34.                                                                               end;                    
  35.                 for i:=1 to lung  do P[i-1]:=StrToInt(rimossi[i]); 
  36.  
  37.     	ANS := 0; 
  38. 	(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  39. 	(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  40.  
  41.   	 for i:=0 to  lung-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; end;
  42.  
  43. 	(*Calculate LIS from left to right for each position*)
  44.  
  45.    	for i := 1 to lung-1 do
  46.            for j:= 0 to i-1 do
  47.                 begin
  48.                   if (P[i] > P[j]) then leftLIS[i] := max(leftLIS[i], leftLIS[j] + 1);                          
  49.                 end;  
  50.  
  51. 	(* Calculate LIS from right to left (decreasing subsequence) for each position*)
  52.  
  53.    	for i := lung - 2 downto 0 do
  54.             for  j := i + 1 to lung-1 do
  55.                begin
  56.                 if (P[i] > P[j]) then rightLIS[i] := max(rightLIS[i], rightLIS[j] + 1);                
  57. 	       end;
  58.         (* Find the maximum length of mountain subsequence*)
  59.  	  maxMountainLength := 0;
  60.   	 for i := 0 to lung-1 do
  61. 	(*A valid mountain peak must have at least one element on both sides*)
  62. 	(*leftLIS[i] > 1 ensures there's at least one element before peak*)
  63. 	(*rightLIS[i] > 1 ensures there's at least one element after peak*)
  64.   	 if (leftLIS[i] >= 1) and (rightLIS[i] >= 1)  then
  65.   	(*Total mountain length with peak at i Subtract 1 because peak is counted in both leftLIS and rightLIS*)
  66.          maxMountainLength := max(maxMountainLength, leftLIS[i] + rightLIS[i] - 1);
  67.  	(* Minimum removals = total elements - maximum mountain length*)
  68.   	 ANS:= N - maxMountainLength; 
  69.         	w:=w+1;
  70.             end;         
  71.           h:=h+1;   
  72.        end;  
  73.    WriteLn(ANS);
  74. end.
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5
0 3 4 2 1
stdout
copy 
0
https://ideone.com/TvDTMk
language:
Pascal (fpc 3.0.4)
created:
16 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!