JOI 2017 Yo 4th

4.cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <cmath>
#include <cstring>

int n, m;
int arr[100010];
int lenDp[(1<<20) + 10000];
int dp[(1 << 20) + 10000];
int sum[25][100010];
int len[25];

const int INF = 1e9;

int calcSum(int type, int st, int en) {
    if(st == 0) {
        return sum[type][en];
    }else {
        return sum[type][en] - sum[type][st - 1];
    }
}

int main() {
    for(int i = 0; i < sizeof(dp) / sizeof(int); ++i) {
        dp[i] = INF;
        lenDp[i] = INF;
    }
    dp[0] = 0;
    lenDp[0] = 0;

    std::cin >> n >> m;

    for(int i = 0; i < n; ++i) {
        std::cin >> arr[i];
        --arr[i];
        ++len[arr[i]];
        ++sum[arr[i]][i];
    }

    for(int i = 0; i < m; ++i) {
        for(int j = 1; j < n; ++j) {
            sum[i][j] += sum[i][j - 1];
        }
    }

    int bitMax = 1 << m;

    for(int i = 0; i < bitMax; ++i) {
        if(dp[i] == INF)
            continue;
        
        for(int j = 0; j < m; ++j) {
            if(i & (1 << j)) {
                continue;
            }
            int newBit = i | (1 << j);

            dp[newBit] = std::min(dp[newBit], dp[i] + (len[j] - calcSum(j, lenDp[i], lenDp[i] + len[j] - 1)));
            lenDp[newBit] = lenDp[i] + len[j];
        }
    }
    std::cout << dp[bitMax - 1] << std::endl;
}