743E.cpp

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const int N = 1000, C = 8; // N: 全部可能的卡片數量，C: 全部可能的顏色數量
int arr[N], n, mid; // arr: 每張卡片的顏色，n: 卡片總數量，mid: 所取每個顏色卡片的最低數量下限 (用 mid 是為了要配合 binary search)
int dp[N][1 << C]; // DP memoization
bool visit[N][1 << C]; // visit memoization
int times[N]; // 記錄每張卡片是第幾次出現自己這個顏色
vector<int> pos[C]; // 記錄每個顏色自己出現的所有位置

int solve(int startIdx, int canNotPickMask) {
    if (canNotPickMask == (1 << C) - 1) return 0; // 如果所有顏色已經全取，剩下的範圍就沒有操作餘地，直接回傳 0
    if (startIdx >= n) return -N; // 如果到尾端還有元素不能取到，代表 mid 取太高，回傳負無限大代表不合理的解，此時最終的 solve(0,0) 必不為正數
    int &ans = dp[startIdx][canNotPickMask];
    if (visit[startIdx][canNotPickMask]) return ans; visit[startIdx][canNotPickMask] = true;
    ans = solve(startIdx + 1, canNotPickMask); // 我先不取 arr[startIdx]，直接把答案給下家決定
    if (((canNotPickMask >> arr[startIdx]) & 1) == 0) { // 如果 arr[startIdx] 這個顏色還沒被取出，而且我想取的話
        int t = times[startIdx]; // 計算 arr[startIdx] 是自己這個顏色出現的第 t 次
        // 那麼再多找 mid - 1 個自己顏色的卡片 (和自己湊 mid 個) 之後會停在哪？答：pos[arr[startIdx]][t + mid - 1]
        // 然後要從下一個開始繼續找其他顏色的，因此下一次起始位置為 pos[arr[startIdx]][t+mid-1] + 1
        if (pos[arr[startIdx]].size() > t + mid - 1) { // 如果確實能取到 mid 張同色卡片的話
            ans = max(ans, mid + solve(pos[arr[startIdx]][t+mid-1] + 1, canNotPickMask | (1 << arr[startIdx])));
            if (pos[arr[startIdx]].size() > t + mid) // 如果確實能取到 (mid + 1) 張同色卡片的話
                ans = max(ans, mid + 1 + solve(pos[arr[startIdx]][t+mid] + 1, canNotPickMask | (1 << arr[startIdx])));
        }
    }
    return ans;
}

int main() { _ // IO 優化
    cin >> n; // 輸入卡片的數量
    set<int> s; // 用來記錄哪些顏色已經出現過
    for (int i=0; i<n; i++) {
        cin >> arr[i]; // 該張卡片的顏色
        arr[i]--; // 同時減一 (規一化) 讓顏色從零開始
        times[i] = pos[arr[i]].size(); // 記錄 i 是第 times[i] 次出現 arr[i] 顏色的卡片，這邊次數會從 0 開始計算
        pos[arr[i]].push_back(i); // 第 times[i] 次出現顏色 arr[i] 的位置為 pos[arr[i]][times[i]]
        s.insert(arr[i]); // 記得有出現該張顏色
    }
    int low = 1, high = n/C, ans = s.size(), temp; // 答案至少為所有卡片曾經用過的顏色數
    while (low <= high) { // 對每個顏色卡片的最低數量下限做 binary search
        mid = (low + high) / 2;
        memset(visit, false, sizeof visit);
        temp = solve(0, 0); // 最低數量下限為 mid 時所算出的答案
        if (temp <= 0) // 若無法滿足需求
            high = mid - 1; // 調低上界
        else { // 符合需求
            ans = max(ans, temp); // 與目前最佳解比看看誰比較快
            low = mid + 1; // 調高下界
        }
    }
    cout << ans << endl; // 輸出答案
    return 0;
}