Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.47 KB | None | 0 0
  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.     while (x0 > 0 || y0 > 0)
  72.     {  
  73.         int dx = x0 - p[x0][y0].first;
  74.         int dy = y0 - p[x0][y0].second;
  75.         if(p[x0][y0].first == 0)
  76.         {
  77.             dx--;
  78.             dy--;
  79.             x0 = 0;
  80.             y0 = 0;
  81.         }
  82.         path += "T";
  83.         path.append(dx, 'R');
  84.         path.append(dy, 'D');
  85.         x0 -= dx;
  86.         y0 -= dy;
  87.     }
  88.  
  89.     cout << ans << endl;
  90.     reverse(path.begin(), path.end());
  91.     cout << path << endl;
  92.     cout << endl;
  93. }
  94.  
  95. int main()
  96. {
  97.     ios_base::sync_with_stdio(0); cin.tie(0);
  98.     int n, m; cin >> m >> n;
  99.     while (!(n == m && m == 0))
  100.     {
  101.         solve(n, m);
  102.         cin >> m >> n;
  103.     }
  104.    
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement