fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Scanner;
  6.  
  7.  class BlackorWhite3 {
  8.  
  9. 	public static void main(String[] args) {
  10. 		   Scanner sc = new Scanner(System.in);
  11. 		   while(true) {
  12.            int n = sc.nextInt();
  13.            if(n== -1)
  14.         	   break;
  15.            Work work = new Work();
  16.            work.solve(sc,n);
  17.  
  18. 		   }
  19. 		   sc.close();
  20. 	}
  21.  
  22. 	static class Work{
  23. 		int dp[][] = new int[201][201];   // number of painted balls 
  24.  
  25. 		List<Integer> lst;
  26. 		int max_val = -1;
  27. 		public void solve(Scanner sc,int n) {
  28. 			lst = new ArrayList<>();
  29.  
  30. 			//lst.add(0);
  31. 			for(int i=0;i<n;i++) {
  32. 				lst.add(sc.nextInt());
  33. 			}
  34.  
  35. 			dp[0][0] =1;
  36. 			for(int x=0;x<n;x++) {
  37. 				for(int y=0;y<n;y++) {
  38.  
  39. 					for(int i=0;i<x;i++) {
  40. 						if(lst.get(i) < lst.get(x)) {
  41. 						     dp[x][y] = dp[x][y] > (dp[i][y]+1) ? dp[x][y] : (dp[i][y]+1);
  42. 						}
  43.  
  44. 					}
  45.  
  46. 					for(int i=0;i<y;i++) {
  47. 						if(lst.get(i) > lst.get(y)) {
  48. 						     dp[x][y] = dp[x][y] > (dp[x][i]+1) ? dp[x][y] : (dp[x][i]+1);
  49. 						}
  50.  
  51. 					}
  52.  
  53. 					max_val = max_val > dp[x][y] ? max_val : dp[x][y];
  54.  
  55. 				}
  56. 			}
  57. 			System.out.println(n-max_val);
  58.  
  59. 			/*for(int x=0;x<n;x++) {
  60. 				for(int y=0;y<n;y++) {
  61. 					System.out.println("dp["+x+"]["+y+"] = " + dp[x][y]);
  62. 				}
  63. 			}*/
  64. 		}
  65. 	}
  66.  
  67. }
  68.  
Success #stdin #stdout 0.13s 29936KB
comments (?)
stdin
copy 
8
1 4 2 3 3 2 4 1
12
7 8 1 2 4 6 3 5 2 1 8 7
-1
stdout
copy 
2
4
https://ideone.com/QDa9jQ
language:
Java (HotSpot 12)
created:
6 years 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!