Advertisement
Josif_tepe

Untitled

Feb 2nd, 2022
1,088
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6. int n, k, S;
  7. int niza[1005];
  8. int dp[15][1005][1005];
  9. int rec(int i, int brnacekori, int brnacevki){
  10.     if(i==S){
  11.         return 0;
  12.     }
  13.  
  14.     if(dp[brnacevki][brnacekori][i]!=-1){
  15.         return dp[brnacevki][brnacekori][i];
  16.     }
  17.  
  18.     int result=0;
  19.     int topka=0;
  20.  
  21.     if(niza[i]==brnacevki){
  22.             topka=1;
  23.     }
  24.  
  25.     result=max(result, rec(i+1, brnacekori, brnacevki)+topka);
  26.  
  27.     if((brnacevki - 1 >= 0)and(brnacekori<k)){
  28.        result=max(result, rec(i+1, brnacekori+1, brnacevki-1)+topka);
  29.        }
  30.     if((brnacevki + 1 < n )and(brnacekori<k)){
  31.        result=max(result, rec(i+1, brnacekori+1, brnacevki+1)+topka);
  32.        }
  33.     dp[brnacevki][brnacekori][i]=result;
  34.        return (result);
  35.  
  36.  
  37.  
  38. }
  39. ///n broj na cevki
  40. ///k broj na dvizenja
  41. ///s golemina na niza
  42. int main()
  43. {
  44.     int t;
  45.     cin >> t;
  46.     while(t--) {
  47. cin>>n>>k>>S;
  48. for(int i=0; i<S; i++){
  49.     cin>>niza[i];
  50.     niza[i]--;
  51. }
  52.  
  53. for(int i=0; i<=n; i++){
  54.     for(int j=0; j<=k; j++){
  55.         for(int k=0; k<=S; k++){
  56.             dp[i][j][k]=-1;
  57.         }
  58.     }
  59. }
  60.        
  61.         int r = rec(0, 0, 0);
  62.         if(k > 0) {
  63.             r = max(r, rec(0, 1, 1));
  64.         }
  65.         cout << r << endl;
  66.     }
  67.     return 0;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement