deushiro

Untitled

Jan 14th, 2020
262
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int mod = 1e9 + 7;
  8.  
  9.  
  10.  
  11.  
  12. int main() {
  13.     ios_base::sync_with_stdio(false);
  14.     cin.tie(0);
  15.     cout.tie(0);
  16.     int n;
  17.     cin >> n;
  18.     vector<pair<int, int>> a(52, {100, -100});
  19.     vector<pair<int, int>> dp(52, {1e9, 1e9});
  20.     vector<bool> flag(51);
  21.     for(int i = 0; i < n; ++i){
  22.         int x, y;
  23.         cin >> x >> y;
  24.         flag[y] = true;
  25.         a[y].first = min(x, a[y].first);
  26.         a[y].second = max(x, a[y].second);
  27.     }
  28.     int st = -1;
  29.     for(int i = 1; i <= 50; ++i){
  30.         if(flag[i]){
  31.             dp[i].first = abs(i - 1) + abs(a[i].second - 1) + abs(a[i].second - a[i].first);
  32.             dp[i].second = abs(i - 1) + abs(a[i].first - 1) + abs(a[i].second - a[i].first);
  33.             st = i + 1;
  34.             break;
  35.         }
  36.     }
  37.     int pr = st - 1;
  38.     for(int i = st; i <= 50; ++i){
  39.         if(flag[i]){
  40.             dp[i].first = min(dp[pr].first + abs(i - pr) + abs(a[i].second - a[pr].first) + abs(a[i].second - a[i].first), dp[i].first);
  41.             dp[i].first = min(dp[i].first, dp[pr].second + abs(i - pr) + abs(a[i].second - a[pr].second) + abs(a[i].second - a[i].first));
  42.             dp[i].second = min(dp[pr].first + abs(i - pr) + abs(a[i].first - a[pr].first) + abs(a[i].second - a[i].first), dp[i].second);
  43.             dp[i].second = min(dp[i].second, dp[pr].second + abs(i - pr) + abs(a[i].first - a[pr].second) + abs(a[i].second - a[i].first));
  44.             pr = i;
  45.         }
  46.  
  47.     }
  48.     cout << min(dp[pr].first, dp[pr].second) << "\n";
  49. }
Advertisement
Add Comment
Please, Sign In to add comment