Từ nhận xét tại mỗi điểm bất kì ta có hai sự lựa chọn và để lựa chọn cuối cùng là tối ưu thì từng vị trí ta luôn chọn phương án tối ưu.

Tạm gọi mảng ~a[]~ là chiều rộng và ~b[]~ là chiều dài.

• Ta gọi ~dp[i][0]~ là phương án tối ưu khi ở vị trí i ta chọn quay chiều rộng song song với ~Ox~
• Và ~dp[i][1]~ là phương án tối ưu khi ở vị trí i ta chọn quay chiều dài song song với ~Ox~

Từ đó ta suy ra: ~\left\{ \begin{array}{rcl} dp[i][0] = a[i] + max(dp[i - 1][0] + |b[i] - b[i - 1]|, dp[i - 1][1] + |b[i] - a[i - 1]|); \\dp[i][1] = b[i] + max(dp[i - 1][0] + |a[i] - b[i - 1]|, dp[i - 1][1] + |a[i] - a[i - 1]|); \end{array}\right.~ ~(1 \le i \le n)~

Giải thích: Ở trường hợp thứ nhất nếu ta chọn quay chiều rộng song song với ~Ox~ ở vị trí ~i~ thì nếu chọn ~dp[i - 1][0]~ tức vị trí trước đó cũng xoay chiều rộng song song thì ta chỉ cộng chênh lệch của chiều dài ~i~ và ~i-1~, ~|b[i] - b[i - 1]|~. Tương tự nếu chọn ~dp[i - 1][1]~ tức vị trí trước đó xoay chiều dài song song thì ta cộng thêm chênh lệch giữa chiều dài ~i~ và chiều rộng ~i-1~ , ~|b[i] - a[i - 1]|~.

Ta có điều tương tự với ~dp[i][1]~.

Cuối cùng kết quả bài toán là ~max(dp[n][1],dp[n][0])~

Độ phức tạp: ~ \mathcal{O}(n).~

Code tham khảo của lds

#include <bits/stdc++.h>
using namespace std;
long long n, a[1000005], b[1000005], f[1000005][2];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);    cout.tie(0);
    memset(f,0,sizeof(f));
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    f[1][0] = a[1];
    f[1][1] = b[1];
    for (int i = 2; i <= n; ++i) {
        f[i][0] = a[i] + max(f[i - 1][0] + abs(b[i] - b[i - 1]), f[i - 1][1] + abs(b[i] - a[i - 1]));
        f[i][1] = b[i] + max(f[i - 1][0] + abs(a[i] - b[i - 1]), f[i - 1][1] + abs(a[i] - a[i - 1]));
    }
    cout << max(f[n][0], f[n][1]);
    return 0;
}

Lưu ý: Vì bài nhập/xuất nhiều nên ta có thể dùng scanf, printf hoặc ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); để tối ưu thời gian.