fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int 
  4. #define pi pair<int ,int >
  5. #define pl pair<ll ,ll >
  6. #define pb push_back
  7. #define vl vector <long long int >
  8. #define vi vector <int >
  9. #define vp vector <pi>
  10. #define mod 1000000007
  11. #define eps 1e-9
  12. #define fi first
  13. #define se second
  14. #define all(x) x.begin(), x.end()
  15. #define _ <<" "<<
  16. #define forn(x,	n) for(int x = 0; x < n ;++ x) 
  17. #define forn1n(x,n) for(int x = 1; x <= n ;++ x)
  18. #define forn1(x,n) for(int x = 1; x < n ;++ x)
  19. #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  20. #pragma GCC optimize ("Ofast")
  21. void scan(){}
  22. template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
  23. int di_; string dnms_, co_ = ",";
  24. void debug_(){cout<<endl;}
  25. template<typename F, typename... R> void debug_(F &f, R&... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
  26. #define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)
  27.  
  28. template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &a){
  29.     return out<<"("<<a.first<<","<<a.second<<")";}
  30. template<class A> ostream& operator<<(ostream& out, const vector<A> &a){
  31. 	out<<"";for(auto it=a.begin();it!=a.end();it++){if(it!=a.begin())out<<" ";out<<*it;}out<<"";
  32. 	return out;}
  33. template<class A, class B> istream& operator>>(istream& in, pair<A,B> &a){in>>a.first>>a.second;return in;}
  34. template<class A> istream& operator>>(istream& in, vector<A> &a){for(A &i:a)in>>i;return in;}
  35.  
  36. const int N = 200+1;
  37. int dp[N][N];
  38. int main(){
  39. 	IOS
  40.  
  41. 	int n;
  42. 	while(1)
  43. 	{
  44. 		cin>>n;
  45. 		memset(dp,0,sizeof(dp));
  46. 		if(n==-1)
  47. 			break;
  48. 		vi v(n);
  49. 		cin>>v;
  50.  
  51. 		dp[0][0]=1;
  52. 		if(v[1]>v[0])
  53. 			dp[1][0] =2;
  54. 		else if(v[1]<v[0])
  55. 			dp[0][1] = 2;
  56. 		for(int x=0;x<n;x++)
  57. 		{
  58. 			for(int y=0;y<n;y++)
  59. 			{
  60. 				if(x==y)
  61. 					continue;
  62. 				for(int i=0;i<x;i++)
  63. 				{
  64. 					if(v[i]<v[x])
  65. 						dp[x][y] = max(dp[i][y] +1,dp[x][y]);
  66. 				}
  67. 				for(int i=0;i<y;i++)
  68. 				{
  69. 					if(v[i]>v[y])
  70. 						dp[x][y] = max(dp[x][i]+1,dp[x][y]);
  71. 				}
  72. 			}
  73. 		}
  74. 		int ans = INT_MIN;
  75. 		forn(i,n)
  76. 		forn(j,n)
  77. 			ans = max(ans,dp[i][j]);
  78.  
  79. 		cout<<n-ans<<endl;
  80.  
  81. 	}
  82.  
  83.  
  84. 	return 0;	
  85. }
Success #stdin #stdout 0s 4400KB
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/TkLSY2
language:
C++14 (gcc 8.3)
created:
4 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!