Advertisement
OIQ

Untitled

OIQ
Jan 14th, 2020
150
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector <vector <int>> a(50, vector <int>(50, 0));
  7. int inf = 1e9;
  8. int mi = 0, mj = 0;
  9.  
  10. int getR(int i) {
  11.     for (int j = mj; j >= 0; j--)
  12.         if (a[i][j] == 1)
  13.             return j;
  14.     return -1;
  15. }
  16.  
  17. int getL(int i) {
  18.     for (int j = 0; j <= mj; j++)
  19.         if (a[i][j] == 1)
  20.             return j;
  21.     return -1;
  22. }
  23.  
  24. int main() {
  25.  
  26.     int n;
  27.     cin >> n;
  28.  
  29.     for (int ii = 0; ii < n; ii++) {
  30.         int i, j;
  31.         cin >> j >> i;
  32.         j--, i--;
  33.         mj = max(mj, j);
  34.         mi = max(mi, i);
  35.         a[i][j] = 1;
  36.     }
  37.  
  38.     vector <vector <int>> dp(mi + 1, vector <int>(mj + 1, inf));
  39.  
  40.     int rf = getR(0);
  41.  
  42.     for (int j = 0; j <= mj; j++) {
  43.         if (rf == -1)
  44.             dp[0][j] = j;
  45.         else {
  46.             if (rf <= j)
  47.                 dp[0][j] = j;
  48.             else
  49.                 dp[0][j] = rf + rf - j;
  50.         }
  51.     }
  52.  
  53.     for (int i = 1; i <= mi; i++) {
  54.         int b = getR(i);
  55.         int a = getL(i);
  56.         for (int k = 0; k <= mj; k++) {
  57.             for (int j = 0; j <= mj; j++) {
  58.                 if (a == -1 && b == -1)
  59.                     dp[i][j] = min(dp[i][j], dp[i-1][k] + 1 + max(k, j) - min(k, j));
  60.                 else {
  61.                     int l = min(k, j);
  62.                     int r = max(k, j);
  63.                     int res = r - l;
  64.  
  65.                     if (a < l)
  66.                         res += 2 * (l - a);
  67.                     if (b > r)
  68.                         res += 2 * (b - r);
  69.                     dp[i][j] = min(dp[i][j], dp[i-1][k] + 1 +  res);
  70.                 }
  71.             }
  72.  
  73.         }
  74.     }
  75.  
  76.     int ans = 1e9;
  77.     for (int j = 0; j <= mj; j++)
  78.         ans = min(ans, dp[mi][j]);
  79.  
  80.     cout << ans;
  81.  
  82.  
  83.  
  84.  
  85.     return 0;
  86. }
Advertisement
RAW Paste Data Copied
Advertisement