Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int ms = 2005;
  9. const ll INF = 1e17;
  10.  
  11. long long dp[ms][ms], c[ms];
  12. int a[ms], b[ms], n, m;
  13. int first[ms], last[ms];
  14. bool cal[ms][ms];
  15.  
  16. ll solve(int i, int j){
  17.     ll &x = dp[i][j];
  18.     if(cal[i][j]) return x;
  19.     cal[i][j] = true;
  20.     x = INF;
  21.  
  22.     if(j == m){
  23.         if(i == n){
  24.             return x = 0;
  25.         }else{
  26.             return x = solve(i + 1, j) + c[i];
  27.         }
  28.     }
  29.  
  30.     if(i == n) return dp[i][j] = INF;
  31.  
  32.     //try to match
  33.     if(a[i] == b[j])
  34.         x = min(x, solve(i + 1, j + 1));
  35.    
  36.     //try to remove
  37.     if(j <= first[a[i]] || j > last[a[i]]){
  38.         ll did = solve(i + 1, j);
  39.         if(did != INF){
  40.             x = min(x, did + c[i]);
  41.         }
  42.     }
  43.     return x;
  44. }
  45.  
  46. int main(){
  47.     freopen("transform.in", "r", stdin);
  48.     int t;
  49.     cin >> t;
  50.     while(t--){
  51.         scanf("%d %d", &n, &m);
  52.         for(int i = 0; i <= n; ++i){
  53.             for(int j = 0; j <= m ; ++j){
  54.                 cal[i][j] = false;
  55.             }
  56.         }
  57.         vector<int> d;
  58.         for(int i = 0; i < n; ++i){
  59.             scanf("%d", &a[i]);
  60.             d.push_back(a[i]);
  61.         }
  62.         for(int i = 0; i < m; ++i){
  63.             scanf("%d", &b[i]);
  64.             d.push_back(b[i]);
  65.         }
  66.         for(int i = 0; i < n; ++i){
  67.             scanf("%lld", &c[i]);
  68.         }
  69.         sort(d.begin(), d.end());
  70.         d.resize(unique(d.begin(), d.end()) - d.begin());
  71.         for(int i = 0; i < (int)d.size(); ++i){
  72.             first[i] = last[i] = -1;
  73.         }
  74.         for(int i = 0; i < n; ++i){
  75.             a[i] = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
  76.         }
  77.         for(int i = 0; i < m; ++i){
  78.             b[i] = lower_bound(d.begin(), d.end(), b[i]) - d.begin();
  79.         }
  80.         for(int i = 0; i < m; ++i){
  81.             last[b[i]] = i;
  82.         }
  83.         for(int i = m - 1; i >= 0; --i){
  84.             first[b[i]] = i;
  85.         }
  86.         ll ans = solve(0, 0);
  87.         if(ans == INF){
  88.             cout << "No\n";
  89.         }else{
  90.             cout << ans << '\n';
  91.         }
  92.     }
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement