Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> ii;
- const int ms = 2005;
- const ll INF = 1e17;
- long long dp[ms][ms], c[ms];
- int a[ms], b[ms], n, m;
- int first[ms], last[ms];
- bool cal[ms][ms];
- ll solve(int i, int j){
- ll &x = dp[i][j];
- if(cal[i][j]) return x;
- cal[i][j] = true;
- x = INF;
- if(j == m){
- if(i == n){
- return x = 0;
- }else{
- return x = solve(i + 1, j) + c[i];
- }
- }
- if(i == n) return dp[i][j] = INF;
- //try to match
- if(a[i] == b[j])
- x = min(x, solve(i + 1, j + 1));
- //try to remove
- if(j <= first[a[i]] || j > last[a[i]]){
- ll did = solve(i + 1, j);
- if(did != INF){
- x = min(x, did + c[i]);
- }
- }
- return x;
- }
- int main(){
- freopen("transform.in", "r", stdin);
- int t;
- cin >> t;
- while(t--){
- scanf("%d %d", &n, &m);
- for(int i = 0; i <= n; ++i){
- for(int j = 0; j <= m ; ++j){
- cal[i][j] = false;
- }
- }
- vector<int> d;
- for(int i = 0; i < n; ++i){
- scanf("%d", &a[i]);
- d.push_back(a[i]);
- }
- for(int i = 0; i < m; ++i){
- scanf("%d", &b[i]);
- d.push_back(b[i]);
- }
- for(int i = 0; i < n; ++i){
- scanf("%lld", &c[i]);
- }
- sort(d.begin(), d.end());
- d.resize(unique(d.begin(), d.end()) - d.begin());
- for(int i = 0; i < (int)d.size(); ++i){
- first[i] = last[i] = -1;
- }
- for(int i = 0; i < n; ++i){
- a[i] = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
- }
- for(int i = 0; i < m; ++i){
- b[i] = lower_bound(d.begin(), d.end(), b[i]) - d.begin();
- }
- for(int i = 0; i < m; ++i){
- last[b[i]] = i;
- }
- for(int i = m - 1; i >= 0; --i){
- first[b[i]] = i;
- }
- ll ans = solve(0, 0);
- if(ans == INF){
- cout << "No\n";
- }else{
- cout << ans << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement