Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int mat[111][111];
- unsigned short d[101][101][101][101];
- pair<int, int> p[111][111];
- void solve(int n, int m)
- {
- for (int i = 1; i <= n; ++i)
- {
- for (int j = 1; j <= m; ++j) cin >> mat[j][i];
- }
- unsigned short ans = 0;
- for (int x1 = 1; x1 <= m; ++x1)
- {
- for (int y1 = 1; y1 <= n; ++y1)
- {
- unsigned short t = 0;
- int px = 0, py = 0;
- for (int x2 = 1; x2 <= m; ++x2)
- {
- for (int y2 = 1; y2 <= n; ++y2)
- {
- if (mat[x1][y1] != mat[x2][y2])
- {
- d[x1][y1][x2][y2] = max(d[x1-1][y1][x2][y2], d[x1][y1-1][x2][y2]);
- if (mat[x1][y1] > mat[x2][y2] && d[x1][y1][x2][y2] > t)
- {
- t = d[x1][y1][x2][y2];
- px = x2;
- py = y2;
- }
- }
- else
- {
- d[x1][y1][x2][y2] = max({d[x1-1][y1][x2][y2], d[x1][y1-1][x2][y2]});
- if (t + 1 > d[x1][y1][x2][y2])
- {
- p[x2][y2] = {px, py};
- d[x1][y1][x2][y2] = t + 1;
- }
- }
- }
- }
- }
- }
- int x0 = m, y0 = n;
- string path = "";
- for (int x = 1; x <= m; ++x)
- {
- for (int y = 1; y <= n; ++y)
- {
- if (d[m][n][x][y] > d[m][n][x0][y0])
- {
- x0 = x;
- y0 = y;
- }
- }
- }
- ans = d[m][n][x0][y0];
- if (x0 != m || y0 != n)
- {
- int dx = m - x0;
- int dy = n - y0;
- path.append(dx, 'R');
- path.append(dy, 'D');
- }
- while (x0 > 0 || y0 > 0)
- {
- int dx = x0 - p[x0][y0].first;
- int dy = y0 - p[x0][y0].second;
- if(p[x0][y0].first == 0)
- {
- dx--;
- dy--;
- x0 = 0;
- y0 = 0;
- }
- path += "T";
- path.append(dx, 'R');
- path.append(dy, 'D');
- x0 -= dx;
- y0 -= dy;
- }
- cout << ans << endl;
- reverse(path.begin(), path.end());
- cout << path << endl;
- cout << endl;
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0);
- int n, m; cin >> m >> n;
- while (!(n == m && m == 0))
- {
- solve(n, m);
- cin >> m >> n;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement