11039 Building designing

題目翻譯

有一批樓板，每塊有長度與顏色（正數、負數代表兩種顏色）。
要堆一棟樓時，樓板長度需要嚴格遞減（由下往上），而且顏色必須交替。
請問最多可以使用幾塊樓板。

輸入

第一行是測試案例數量。
每個案例的第一行是整數 p，代表可用的樓層材料數量。
接下來 p 行每行有一個非零整數，其絕對值代表樓層大小，正負號代表顏色。

輸出

對於每個案例，輸出一個整數，代表符合規則（大小遞減且顏色交替）的最大樓層總數。

解題思路

這份程式把每塊樓板轉成 (絕對值長度, 顏色)：

1. 正數視為顏色 0，負數視為顏色 1，長度取絕對值。
2. 依長度排序後去重，再反轉成「由大到小」處理，確保後面接上的樓板都更短。
3. 用 dp[2]： dp[c] 表示目前以顏色 c 結尾時，最多可堆幾塊。
4. 處理一塊顏色 c 的樓板時，可接在另一色 1-c 後面： dp[c] = max(dp[c], dp[1-c] + 1)。

最後答案是 max(dp[0], dp[1])。

這樣做的關鍵是先把長度順序固定成遞減，接著只要處理顏色交替即可。

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define idonthavegirlfriend ios::sync_with_stdio(0), cin.tie(0);
#define pb push_back
#define yn(a) (a ? "Yes\n" : "No\n")
// #include <atcoder/fenwicktree>
// #include <atcoder/dsu>
// using namespace atcoder
// author:Jackis666

signed main() {
    idonthavegirlfriend
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<pair<int, int>> a(n);
        for (int i = 0; i < n; i++) {
            int in;
            cin >> in;
            if (in > 0) {
                a[i] = {in, 0};
            } else {
                a[i] = {-1 * in, 1};
            }
        }
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        reverse(a.begin(), a.end());
        int dp[2] = {0, 0};
        for (int i = 0; i < a.size(); i++) {
            dp[a[i].second] = max(dp[a[i].second], dp[1 - a[i].second] + 1);
        }
        cout << max(dp[0], dp[1]) << "\n";
    }
}

也可以使用排序後貪心

//author: Piau
#include <bits/stdc++.h>
using namespace std;

#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long

signed main() { WA();
    int t; for (cin >> t; t--;) {
        int n; cin >> n;
        if (!n) {
            cout << "0\n";
            continue;
        }
        vector<int> v(n);
        for (auto &i : v) cin >> i;
        sort(all(v), [](int a, int b) {
            return abs(a) > abs(b);
        });
        int k = v.front() > 0 ? 1 : -1 , cnt = 1;
        for (auto &i : v) if (k*i < 0) k *= -1, cnt++;
        cout << cnt << '\n';
    }
}