ccbeginner

TIOJ 1051 (RE)

Oct 8th, 2020
801
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define SZ(X) (int)(X).size()
  5.  
  6. int arr[513], brr[513];
  7. int dp[513];
  8. int back[513];
  9.  
  10. struct state{
  11.     int v,p,q;
  12.     bool operator<(const state &rhs)const{
  13.         return v > rhs.v;
  14.     }
  15. };
  16. vector<state> idxs;
  17.  
  18. int32_t main(){
  19.     int t;
  20.     cin >> t;
  21.     while(t--){
  22.         idxs.clear();
  23.         int n;
  24.         cin >> n;
  25.         for(int i = 1; i <= n; ++i)cin >> arr[i];
  26.         for(int i = 1; i <= n; ++i)cin >> brr[i];
  27.         for(int i = 1; i <= n; ++i){
  28.             for(int j = 1; j <= n; ++j){
  29.                 if(arr[i] == brr[j]){
  30.                     state tmp = {.v = arr[i], .p = i, .q = j};
  31.                     idxs.emplace_back(tmp);
  32.                 }
  33.             }
  34.         }
  35.         sort(idxs.begin(), idxs.end());
  36.         dp[0] = 1;
  37.         back[0] = -1;
  38.         int ans = 0;
  39.         for(int i = 1; i < SZ(idxs); ++i){
  40.             dp[i] = 1;
  41.             back[i] = -1;
  42.             for(int j = 0; j < i; ++j){
  43.                 if(idxs[i].p > idxs[j].p && idxs[i].q > idxs[j].q && dp[i] < dp[j]+1){
  44.                     dp[i] = dp[j]+1;
  45.                     back[i] = j;
  46.                 }
  47.             }
  48.             if(dp[i] > dp[ans])ans = i;
  49.         }
  50.         vector<int> out;
  51.         while(ans != -1){
  52.             out.emplace_back(idxs[ans].v);
  53.             ans = back[ans];
  54.         }
  55.         reverse(out.begin(), out.end());
  56.         for(int i = 0; i < SZ(out); ++i)cout << out[i] << ' ';
  57.         cout << endl;
  58.     }
  59.     return 0;
  60. }
RAW Paste Data