b006: 矩形旋轉 解題心得

題目來源：https://zerojudge.tw/ShowProblem?problemid=b006

內容

給定若干個各種長寬的矩形，請求出最多有多少個矩形可以疊在一起使得上方的矩形其長與寬均不大於下方的矩形。注意，上下矩形的邊必須平行，也就是說矩形可以 90 度旋轉或不旋轉但是不能轉其他角度。

輸入說明
每一行的第一個數字為矩形的個數 n，接著有 2n 個正整數，分別為第一個 矩形的長與寬、第二個矩形的長與寬、…。所有的數字皆以空白間格，數字不大 於 30000。例如下面範例的第一行代表有三個矩形尺寸分別為 1×5、2×3、3×2， 對於此輸入可以有兩個矩形疊在一起。

輸出說明
依序每一行輸出每一個案例所求之值。

範例輸入 #1                               範例輸出 #1
3                                                  2
1 5 2 3 3 2                                   4
5
1 1 4 8 5 6 6 7 7 7

第一、其實這題題目的測資很軟，錯的上傳也會是對的，就像我第一眼看到這程式的時候，我把它誤解成跟b966: 第 3 題 線段覆蓋長度一樣的題目了(點題目可以看到我該題的解法)，所以我用pair來裝矩形的兩邊，將長邊都放到pair的first，短邊放到second...。
附上錯誤的程式碼如下：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    while(cin >> n) {
        int m = 0;
        vector<pair<int , int>> vp;
        while(m++ < n) {
            int x , y;
            cin >> x >> y;
            pair<int , int> p;
            if(x > y) {
                p.first = x;    p.second = y;
            } else {
                p.first = y;    p.second = x;
            }
            vp.push_back(p);
            
        }
        sort(vp.begin() , vp.end());
        int count = 0;
        int max = 0;
        for(int i = n-1; i > 0 ; i--) {
            //cout << "vp[i].second = " << vp[i].second << " vp[i-1].second = " << vp[i-1].second <<" i = " << i << endl;;
            if(vp[i].second < vp[i-1].second) {
                if(max < count) max = count;
                count = 0;
            } else {
                if(count == 0) {
                    count = 2;
                } else
                    count++;
            }
        }
        if(max < count) max = count;
        cout << max <<endl;
    }

    return 0;
}

上面的程式問題在於如果面對(5 4)(4 4)(2 7)(2 1)(1 1)，程式會判定疊成兩堆分別為(5 4)(4 4)跟(2 7)(2 1)(1 1)，但其實正確答案是(5 4)(4 4)(2 1)(1 1 )。

仔細觀察測資後發現，(5 4)(4 4)(2 7)(2 1)(1 1)我們可以由小到大依序判別自己最多可以跟幾個矩形交疊。
ex.
1 1(自己跟自己玩，只能疊一個)
2 1前面只有1 1可以疊所以他可以疊1+1個(包含自己)
2 7前面有1 1 跟 2 1可以疊選擇1 1就是疊兩個選擇2 1就是疊2+1(含自己)個
4 4前面有2 7.  2 1. 1 1可以選，結論是選可惜2 7不能選，所以選2 1來疊總共疊2+1(含自己)個
5 4前面有4 4. 2 7. 2 1. 1 1可以選4 4跟2 7最有利但是2 7不能選，所以選4 4故總共3+1個

以下附上正確的程式碼：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    int m = 0, x, y;
    int count;
    int max;
    vector<pair<int, int>> vp;
    vector<int> cuc;
    while (cin >> n) {
        m = 0;
        vp.clear();
        cuc.clear();
        while (m++ < n) {
            cin >> x >> y;
            pair<int, int> p;
            if (x > y) {
                p.first = x;    p.second = y;
            }
            else {
                p.first = y;    p.second = x;
            }
            vp.push_back(p);

        }
        sort(vp.begin(), vp.end());
        max = 1;
        for (int i = 0; i < n; i++) {
            count = 1;
            for (int j = i-1; j >= 0; j--) {
                if (vp[i].second >= vp[j].second) {
                    if (max < count + cuc[j]) {
                        max = count + cuc[j];
                    }
                }
            }
            cuc.push_back(max);
        }
        cout << max << "\n";

        
    }

    return 0;
}