fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. int n,a[205],dp[205][205][205],w[205][205],b[205][205],bw[205];
  5. int solve(int lb,int lw,int i)
  6. {			
  7. 	if(i==(n-1))
  8. 	{
  9. 		if(lb==-1 || lw==-1 || a[i]>a[lb] || a[i]<a[lw])
  10. 			return 1;
  11. 		else
  12. 			return 0;
  13. 	}
  14. 	int a1=INT_MIN,a2=INT_MIN,a3=INT_MIN,ans=INT_MIN;
  15. 	if(lb==-1 || a[i]>a[lb])
  16. 		a1=1+solve(i,lw,i+1);	
  17. 	if(lw==-1 || a[i]<a[lw])
  18. 		a2=1+solve(lb,i,i+1);
  19. 	a3=solve(lb,lw,i+1);
  20. 	return max(a3,max(a2,a1));
  21. }
  22. int solve1(int lb,int lw,int i)
  23. {
  24. 	if(lb==-1 && lw==-1)
  25. 	{
  26. 		if(bw[i]!=-1)
  27. 			return bw[i];
  28. 	}
  29. 	else
  30. 		if(lb==-1 && lw!=-1)
  31. 		{
  32. 			if(w[lw][i]!=-1)
  33. 				return w[lw][i];
  34. 		}
  35. 		else
  36. 			if(lb!=-1 && lw==-1)
  37. 			{
  38. 				if(b[lb][i] !=-1)
  39. 					return b[lb][i];
  40. 			}
  41. 			else
  42. 				if(lb!=-1 && lw!=-1)
  43. 				{
  44. 					if(dp[lb][lw][i]!=-1)
  45. 						return dp[lb][lw][i];
  46. 				}
  47.  
  48. 	if(i==(n-1))
  49. 	{
  50. 		if(lb==-1 || lw==-1 || a[i]>a[lb] || a[i]<a[lw])
  51. 		{
  52. 			if(lb==-1 && lw==-1)
  53. 	{
  54. 		bw[i]=1;
  55. 			return 1;
  56. 	}
  57. 	else
  58. 		if(lb==-1 && lw!=-1)
  59. 		{
  60. 			w[lw][i]=1;
  61. 				return 1;
  62. 		}
  63. 		else
  64. 			if(lb!=-1 && lw==-1)
  65. 			{
  66. 				b[lb][i] =1;
  67. 					return 1;
  68. 			}
  69. 			else
  70. 				if(lb!=-1 && lw!=-1)
  71. 				{
  72. 					dp[lb][lw][i]=1;
  73. 						return 1;
  74. 				}
  75.  
  76. 		}
  77. 		else
  78. 		{
  79. 			dp[lb][lw][i]=0;
  80. 			return 0;
  81. 		}
  82. 	}
  83. 	int a1=INT_MIN,a2=INT_MIN,a3=INT_MIN,ans=INT_MIN;
  84. 	if(lb==-1 || a[i]>a[lb])
  85. 		a1=1+solve1(i,lw,i+1);	
  86. 	if(lw==-1 || a[i]<a[lw])
  87. 		a2=1+solve1(lb,i,i+1);
  88. 	a3=solve1(lb,lw,i+1);
  89. 	ans=max(a3,max(a2,a1));
  90.  
  91. 		if(lb==-1 && lw==-1)
  92. 	{
  93. 		bw[i]=ans;
  94. 			return ans;
  95. 	}
  96. 	else
  97. 		if(lb==-1 && lw!=-1)
  98. 		{
  99. 			w[lw][i]=ans;
  100. 				return ans;
  101. 		}
  102. 		else
  103. 			if(lb!=-1 && lw==-1)
  104. 			{
  105. 				b[lb][i] =ans;
  106. 					return ans;
  107. 			}
  108. 			else
  109. 				if(lb!=-1 && lw!=-1)
  110. 				{
  111. 					dp[lb][lw][i]=ans;
  112. 						return ans;
  113. 				}
  114.  
  115. }
  116. int main()
  117. {
  118.     ios_base::sync_with_stdio(false);
  119.     cin.tie(NULL);
  120.     while(1)
  121.     {
  122.     	memset(dp,-1,sizeof(dp));
  123.     	memset(b,-1,sizeof(b));
  124.     	memset(w,-1,sizeof(w));
  125.     	memset(bw,-1,sizeof(bw));
  126.     	cin>>n;
  127.     	if(n==-1)
  128.     		break;
  129.     	for(int i=0;i<n;i++)
  130.     	{
  131.     		cin>>a[i];
  132.     	}
  133.     	cout<<(n-solve1(-1,-1,0))<<endl;
  134.     }
  135.     return 0;
  136. }
  137.  
Runtime error #stdin #stdout 0.02s 36784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MjTflM
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!