P11652 [COCI 2024/2025 #4] 鞋 / Cipele 我的代码：

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

using namespace std;

const int MAXN = 2e5 + 5;
const int MAXQ = 1e6 + 5;

int n, m, q;
int a[MAXQ];

// 计算鞋在鞋柜中的位置
int getPosition(int target, int state) {
    int pos = 1;
    for (int i = 1; i <= n; ++i) {
        if ((state & (1 << (i - 1))) == 0) {
            if (i == target) {
                return pos;
            }
            ++pos;
        }
    }
    return 0; // 鞋在走廊
}

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> a[i];
    }

    // 使用 vector 动态分配 dp 数组
    vector<vector<int>> dp(q + 1, vector<int>(1 << n, INT_MAX));
    dp[0][0] = 0;

    for (int i = 1; i <= q; ++i) {
        for (int state = 0; state < (1 << n); ++state) {
            if (dp[i - 1][state] == INT_MAX) continue;

            int target = a[i];
            int pos = getPosition(target, state);
            int cost = pos;

            // 情况 1：将鞋放在走廊
            if (__builtin_popcount(state) < m) {
                int newState = state | (1 << (target - 1));
                dp[i][newState] = min(dp[i][newState], dp[i - 1][state] + cost);
            }

            // 情况 2：将鞋放回鞋柜
            dp[i][state] = min(dp[i][state], dp[i - 1][state] + cost);
        }
    }

    int ans = INT_MAX;
    for (int state = 0; state < (1 << n); ++state) {
        ans = min(ans, dp[q][state]);
    }

    cout << ans << endl;

    return 0;
}

评测结果：https://www.luogu.com.cn/record/201208006 我已经无话可说了……