fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define all(x) x.begin(),x.end()
  4. #define rall(x) x.rbegin(),x.rend()
  5. const int MAX = 1e6+7;
  6. const int MOD = 1e9+7;
  7. #define ll long long int
  8.  
  9. int n;
  10. int vi[501];
  11. int dp[501][501][501];
  12.  
  13. ll Min(ll a , ll b){
  14.   return a<=b ? a : b;
  15. }
  16.  
  17. ll solve(int i,int x,int last){
  18.  
  19.   if(i == n) return 0;
  20.   if(dp[i][x][last]!=-1) return dp[i][x][last];
  21.  
  22.  
  23.   int mn = INT_MAX;
  24.   if(i == 0)
  25.     mn = Min(solve(i+1,x,vi[0]),1+solve(i+1,vi[0],x));
  26.   else{
  27.  
  28.       if(vi[i]>=last){
  29.           mn = Min(solve(i+1,x,vi[i]),1+solve(i+1,vi[i],x));
  30.       }else if(x>=last) mn = 1+solve(i+1,vi[i],x);
  31.       else mn = INT_MAX;
  32.   }
  33.  
  34.   dp[i][x][last] =  mn;
  35.   return mn;
  36.  
  37. }
  38.  
  39. int main(){
  40.  
  41.   ios_base::sync_with_stdio(0);
  42.   cin.tie(0); cout.tie(0);
  43.  
  44.   int t;
  45.   cin>>t;
  46.  
  47.   while(t-->0){
  48.  
  49. 	memset(vi,0,sizeof(vi));
  50. 	int p;
  51.     cin>>n>>p;
  52.     for(int i = 0;i<n;i++) cin>>vi[i];
  53.  
  54.     for(int i = 0;i<501;i++){
  55.       for(int j = 0;j<501;j++){
  56.         for(int k = 0;k<501;k++) dp[i][j][k] = -1;
  57.       }
  58.     }
  59.  
  60.     ll mx = solve(0,p,0);
  61.     if(mx>=INT_MAX) cout<<-1<<'\n';
  62.     else cout<<mx<<'\n';
  63.   }
  64.  
  65.   return 0;
  66. }
  67.  
Success #stdin #stdout 0.48s 494568KB
comments (?)
stdin
copy 
6
4 1
2 3 5 4
5 6
1 1 3 4 4
1 10
2
2 10
11 9
2 10
12 11
5 18
81 324 218 413 324
stdout
copy 
1
0
0
2
1
2
https://ideone.com/i3lWQr
language:
C++14 (gcc 8.3)
created:
3 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!