SHARE
TWEET

Untitled

a guest Feb 23rd, 2020 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int mat[111][111];
  7. unsigned short d[101][101][101][101];
  8. pair<int, int> p[111][111];
  9.  
  10. void solve(int n, int m)
  11. {
  12.     for (int i = 1; i <= n; ++i)
  13.     {
  14.         for (int j = 1; j <= m; ++j) cin >> mat[j][i];
  15.     }
  16.  
  17.     unsigned short ans = 0;
  18.  
  19.     for (int x1 = 1; x1 <= m; ++x1)
  20.     {
  21.         for (int y1 = 1; y1 <= n; ++y1)
  22.         {
  23.             unsigned short t = 0;
  24.             int px = 0, py = 0;
  25.             for (int x2 = 1; x2 <= m; ++x2)
  26.             {
  27.                 for (int y2 = 1; y2 <= n; ++y2)
  28.                 {
  29.                     if (mat[x1][y1] != mat[x2][y2])
  30.                     {
  31.                         d[x1][y1][x2][y2] = max(d[x1-1][y1][x2][y2], d[x1][y1-1][x2][y2]);
  32.                         if (mat[x1][y1] > mat[x2][y2] && d[x1][y1][x2][y2] > t)
  33.                         {
  34.                             t = d[x1][y1][x2][y2];
  35.                             px = x2;
  36.                             py = y2;
  37.                         }
  38.                     }
  39.                     else
  40.                     {
  41.                         d[x1][y1][x2][y2] = max({d[x1-1][y1][x2][y2], d[x1][y1-1][x2][y2]});
  42.                         if (t + 1 > d[x1][y1][x2][y2])
  43.                         {
  44.                             p[x2][y2] = {px, py};
  45.                             d[x1][y1][x2][y2] = t + 1;
  46.                         }
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.     }
  52.     int x0 = m, y0 = n;
  53.  
  54.     string path = "";
  55.  
  56.     for (int x = 1; x <= m; ++x)
  57.     {
  58.         for (int y = 1; y <= n; ++y)
  59.         {
  60.             if (d[m][n][x][y] > d[m][n][x0][y0])
  61.             {
  62.                 x0 = x;
  63.                 y0 = y;
  64.             }
  65.         }
  66.     }
  67.  
  68.     ans = d[m][n][x0][y0];
  69.  
  70.  
  71.     if (x0 != m || y0 != n)
  72.     {
  73.         int dx = m - x0;
  74.         int dy = n - y0;
  75.         path.append(dx, 'R');
  76.         path.append(dy, 'D');
  77.     }
  78.  
  79.     while (x0 > 0 || y0 > 0)
  80.     {  
  81.         int dx = x0 - p[x0][y0].first;
  82.         int dy = y0 - p[x0][y0].second;
  83.         if(p[x0][y0].first == 0)
  84.         {
  85.             dx--;
  86.             dy--;
  87.             x0 = 0;
  88.             y0 = 0;
  89.         }
  90.         path += "T";
  91.         path.append(dx, 'R');
  92.         path.append(dy, 'D');
  93.         x0 -= dx;
  94.         y0 -= dy;
  95.     }
  96.  
  97.     cout << ans << endl;
  98.     reverse(path.begin(), path.end());
  99.     cout << path << endl;
  100.     cout << endl;
  101. }
  102.  
  103. int main()
  104. {
  105.     ios_base::sync_with_stdio(0); cin.tie(0);
  106.     int n, m; cin >> m >> n;
  107.     while (!(n == m && m == 0))
  108.     {
  109.         solve(n, m);
  110.         cin >> m >> n;
  111.     }
  112.    
  113. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top