fork(1) download
copy 
  1. //AUTHOR: Vivek Shah (@vivek_shah98)
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define ll long long 
  7. #define mod 1000000007
  8. #define debug(x) cout << #x << " is " << x << endl;
  9. #define debug1 cout << "YES" <<endl;
  10. #define llt int test;cin>>test;while(test--)
  11. #define pb push_back
  12. #define setto(n) cout << fixed<< setprecision(n)
  13. #define fi first
  14. #define se second
  15. #define sz(i) int(i.size())
  16. #define all(v) v.begin(),v.end()
  17. #define mem(a, b) memset(a, b, sizeof(a))
  18. #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  19. #define F(i,n) rep(i,0,n)
  20. #define len(s) s.length()
  21. #define MAX 1000
  22.  
  23. using namespace std;
  24.  
  25. int A[MAX], n, k, len0, len, len1;
  26.  
  27. int dp[MAX][51][51]; 
  28.  
  29. int longest_subseq(int ix, int available_k, int last_val){
  30.     if(dp[ix][available_k][last_val] >= 0)
  31.         return dp[ix][available_k][last_val];
  32.  
  33.     if (ix == n or available_k < 0)
  34.         return 0;
  35.  
  36.     len0 = longest_subseq(ix+1, available_k, last_val);
  37.  
  38.     if (abs(A[ix] - last_val) > available_k)//don't include
  39.         return dp[ix][available_k][last_val] = len0;
  40.  
  41.     len1 = 1 + longest_subseq(ix+1, available_k-abs(A[ix]-last_val), A[ix]);
  42.  
  43.     return dp[ix][available_k][last_val] = max(len0, len1);
  44. }
  45.  
  46.  
  47. int main(){
  48.  
  49.     boost;
  50.  
  51.     cin>>n>>k;
  52.  
  53.  
  54.     rep(i,0,n)
  55.         rep(j,0,51)
  56.             rep(k,0,51)
  57.                 dp[i][j][k] = -INT_MAX;
  58.  
  59.     F(i,n)cin>>A[i];
  60.  
  61.     int xx = longest_subseq(0, k, A[0]);
  62.     cout<<xx;
  63.  
  64.     // int ans[MAX], ma = INT_MIN;
  65.     // for (int i = 0; i <n ; ++i){
  66.     //     ans[i] = -INT_MAX;
  67.     //     for (int j = 0; j <51 ; ++j)
  68.     //         for (int k = 0; k <51 ; ++k)
  69.     //             ans[i] = max(ans[i], dp[i][j][k]);
  70.     //     ma = max(ans[i], ma);
  71.     // }
  72.  
  73.     // cout<<max(ma, xx);
  74.  
  75.     return 0;
  76. }
  77.  
  78. // 4 5
  79. // 1 2 50 6
  80. //Ans = 3
  81.  
  82. // 9 10
  83. // 5 2 4 9 1 3 2 4 5
  84. //Ans = 7
  85.  
  86. // 5 0 
  87. // 1 1 1 1 1 
  88. //Ans = 5
Success #stdin #stdout 0s 25400KB
comments (?)
stdin
copy 
4 5
1 2 50 6
stdout
copy 
3
https://ideone.com/6kI7iZ
language:
C++14 (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!