CWOI S C0324 A 分组

题意

U2FsdGVkX199WJF0kSHD1icITzJoRgvSazdEQqOBO28m3PhgvTrFHmOyUqzTFjjo
ixzCMhdP2BK/IV8D8MxVD5d+2mhNg7irYgb670leYQiTH2WTIE/OkyyqOrZDNJUg
kc8S/kU9PAHRqVAoMYXGBAClulesWGnPDS2UTW0GCRWqZgzI6KDp5rKPFnkB8adv
mSG/fbwjcDNbGotCPzkxxfY0eTwJoxo9RCEwA6WA/VtgKDQqmYloEY3jRGc2GwpT
bS5k8XHPg68YZmoWlNggoIzJSA/OjrArLP5jfyfrel37QMaF9eB5CHRXyKq6z8RJ
RVX14Pa6Ogi8QHoeyeQ6j61fFddXt+zwNECfJlGyuGkztZZ7R9IJP1m6CwW0HZzY
yBitX1AvpP3RVWMREg4jvlfhp+r9fkwnuYb0NXN6x+GZBwfhpQk6LLdgCAvqWKdv
sgJvqFG8Yla7CwNOWbgpQQ==

解析

首先可以将所有人排序，以经验为第一关键字，如果经验相同则比较意愿，保证同一组内，组员在组长前面。

令 f(i, j, k) 表示考虑前 i 个人，已经有 j 个完整的组了，有 k 个组只有组员没有组长。容易得到转移，复杂度 $O(NK^2)$。

比较妙的一点是，如果 $2K > N$，明显是不可行的，可以直接输出无解。所以实际上在 dp 时，有 $2K \le N$ 和 $NK \le 10^5$，即 $K \le \sqrt{5\times 10^4}$，故上面的 $O(NK^2)$ 可以通过。

#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>

struct node_t
{
	int w, s, p;
	node_t(int w, int s, int p) : w(w), s(s), p(p) {}
};

constexpr long long INF = std::numeric_limits<long long>::max();

int main()
{
	int n, k;
	std::cin >> n >> k;

	if (k * 2 > n) {
		std::cout << -1 << std::endl;
		return 0;
	}

	std::vector<node_t> a;
	a.reserve(n);
	for (int i = 0; i < n; i++) {
		int w, s, p;
		std::cin >> w >> s >> p;
		a.emplace_back(w, s, p);
	}

	std::sort(a.begin(), a.end(),
		  [](node_t a, node_t b)
		  {
			  if (a.w != b.w) {
				  return a.w < b.w;
			  } else {
				  return (a.p == 2 && b.p == 3) ||
					  (a.p == 3 && b.p == 1) ||
					  (a.p == 2 && b.p == 1);
			  }
		  });

	std::vector f(k + 1, std::vector<long long>(k + 1, INF));
	f[0][0] = 0;
	for (int i = 0; i < n; i++) {
		std::vector g(k + 1, std::vector<long long>(k + 1, INF));
		for (int x = 0; x <= k; x++) {
			for (int y = 0; y <= k; y++) {
				if (f[x][y] == INF) continue;
				g[x][y] = std::min(g[x][y], f[x][y]);
				if (a[i].p != 2 && x + 1 <= k && y - 1 >= 0) g[x + 1][y - 1] = std::min(g[x + 1][y - 1], f[x][y] + a[i].s);
				if (a[i].p != 1 && y + 1 <= k) g[x][y + 1] = std::min(g[x][y + 1], f[x][y] + a[i].s);
			}
		}
		f = std::move(g);
	}

	if (f[k][0] == INF) std::cout << -1 << std::endl;
	else std::cout << f[k][0] << std::endl;
}