题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

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

using namespace std;

const int N = 1010;

int n, m;
int p[N], color[N];
vector<int> dog[N];
int f[N][N], g[N][N];

int main()
{
    int T;
    cin >> T;
    for (int cases = 1; cases <= T; cases ++)
    {
        cin >> n >> m;

        for (int i = 0; i < n; i ++) cin >> p[i];
        for (int i = 0; i < n; i ++) cin >> color[i];

        for (int i = 1; i <= 1000; i ++) dog[i].clear();
        for (int i = 0; i < n; i ++) dog[color[i]].push_back(p[i]);

        for (int i = 1; i <= 1000; i ++) sort(dog[i].begin(), dog[i].end());

        memset(f, 0x3f, sizeof f);
        memset(g, 0x3f, sizeof g);

        f[0][0] = g[1001][0] = 0;

        for (int i = 1; i <= 1000; i ++)
            for (int j = 0; j <= m; j ++)
            {
                f[i][j] = f[i - 1][j];
                for (int k = 0; k < dog[i].size() && k + 1<= j; k ++)
                    f[i][j] = min(f[i][j], f[i - 1][j - k - 1] + 2 * dog[i][k]);
            }

        for (int i = 1000; i; i --)
            for (int j = 0; j <= m; j ++)
            {
                g[i][j] = g[i + 1][j];
                for (int k = 0; k < dog[i].size() && k + 1 <= j; k ++)
                    g[i][j] = min(g[i][j], g[i + 1][j - k - 1] + 2 * dog[i][k]);
            }

        int res = 1e9;
        for (int i = 1; i <= 1000; i ++)
            for (int j = 0; j < dog[i].size(); j ++)
                for (int k = 0; k + j + 1 <= m; k ++)
                    res = min(res, f[i - 1][k] + g[i + 1][m - k - j - 1] + dog[i][j]);

        printf("Case #%d: %d\n", cases, res);
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla