「题解」洛谷 P7878 「SWTR-07」My rating is 1064（hard version）

特判掉 (k=2)．

显然，所有集合都用最优。

注意到如果用了 (xgeq 2) 个集合，那么把剩下的数中最大的 ((k-x)) 个单独放一个集合，多余的数，一定能选出一个集合来放进去使得不会对答案产生负贡献。

枚举第一个放入第二个集合是哪个元素 (x)，在它之前的一定放在同一个集合里面，这样我们再知道剩余 ((n-x)) 个元素中最大的 ((k-2)) 个是多少就可以快速计算这种放法的答案了，拿个 multiset 预处理一下即可。

容易发现这样做所有情况都考虑了进去，是不重不漏的。

时间复杂度大概是个 (mathcal{O}(Tnlog n))．

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
typedef long long ll;
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T &read(T &r) {
	r = 0; bool w = 0; char ch = getchar();
	while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
	return r = w ? -r : r;
}
const int N = 114514;
int n, k;
int a[N];
ll sum, ans, b[N];
void solve() {
	read(n); read(k); sum = 0;
	for(int i = 1; i <= n; ++i) read(a[i]), b[i] = 0;
	std::multiset<int>st;
	if(n == k) {
		for(int i = 1; i <= n; ++i) sum += a[i];
		printf("%lld
", sum);
		return ;
	}
	k -= 2;
	if(k) {
		for(int i = n; i >= n-k+1; --i) sum += a[i], st.insert(a[i]);
		b[n-k] = sum;
		for(int i = n-k; i >= 3; --i) {
			if(*st.begin() < a[i]) {
				sum -= *st.begin();
				st.erase(st.begin());
				st.insert(a[i]);
				sum += a[i];
			}
			b[i-1] = sum;
		}
	}
	ans = sum = 0;
	sum = a[1];
	for(int i = 2; i <= n-k; ++i) {
		ans = Max(ans, sum + b[i] + a[i]);
		sum -= Min(a[i], a[i-1]);
	}
	printf("%lld
", ans);
}
signed main() {
	int meishayong; read(meishayong);
	int T; read(T);
	while(T--) solve();
	return 0;
}