2024/7/2 T1

题意：

分析：

记 \(S_{i}\) 表示目前第 \(i\) 个集合里的元素个数。

集合之间互不区分，强制钦定必须满足 \(S_{i} \le S_{i+1}(i<k)\)。

经搜索发现，这样的状态数量最多约为 \(1.8 \times 10^5\)。

极差可以这样处理：将 \(a\) 排序，\(S_{i}\) 第一次加入某个元素 \(x\)，则贡献加上 \(-x\)；\(S_{i}\) 被 \(y\) 填满，则贡献加上 \(+y\)。

这样看起来可以 dp，但还有一个问题：如何处理每个集合的元素必须互不相同呢？

可以强制要求所有相同的元素必须以一个固定的顺序加入，使得其在不同的集合，可以从大到小加或从小到大加（元素个数）。这里采用前者。

f[S][j]表示(从小往大填)已经填了i(∑S[i])个数,第i个数在加入后它目前在的集合的大小为j
当我们填入a[i+1]时,如果a[i+1]=a[i],则需要保证a[i+1]填入的集合的大小小于j即可 

然后做完了！

时隔 \(7\) 个月，以前的我看不懂题解，但现在我 AC 了，牛不牛。

#include<bits/stdc++.h>
#define N 110
#define int long long
#define base 131
using namespace std;
bool s1;

int n, k, len;
int a[N], now[N];

vector<int>z[110];
int S[200005][110];
int tot;

unordered_map<int, int>id;

void dfs(int x, int lst) {
	if(x > k) {
		tot++;
		int g = 0;
		int num = 0;
		for(int i = 1; i <= k; i++) {
			S[tot][i] = now[i];
			g += now[i];
			num = num * base + now[i];
		}
		id[num] = tot;
		z[g].push_back(tot);
		//cout << tot << endl;
		return;
	}
	for(int i = lst; i <= len; i++) {
		now[x] = i;
		dfs(x + 1, i);
	}
}

int f[200005][110];
//f[S][j]表示(从小往大填)已经填了i(∑S[i])个数,第i个数在加入后它目前在的集合的大小为j
//当我们填入a[i+1]时,如果a[i+1]=a[i],则需要保证a[i+1]填入的集合的大小小于j即可 

void upd(int &x, int y) {
	x = min(x, y);	
}

bool s2;
signed main() {
	//freopen("diyiti06.in", "r", stdin);
	//ios::sync_with_stdio(0);
	//cin.tie(0); cout.tie(0);
	//cerr << (&s1 - &s2) / 1024 / 1024 << " MB\n";
	cin >> n >> k;
	len = n / k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	/*if(k == n) {
		cout << 0;
		return 0;
	}*/ 
	sort(a + 1, a + n + 1);
	dfs(1, 0);
	//cerr << "e";
	for(int S = 1; S <= tot; S++)
	for(int j = 0; j <= len; j++) f[S][j] = 1e18;
	
	/*for(int s = 1; s <= tot; s++) {
		cout << "S " << s << " : ";
		for(int j = 1; j <= len; j++) cout << S[s][j] << " ";
		cout << endl;
	}
	
	for(int i = 1; i <= n; i++) {
		cout << i << " : ";
		for(auto x : z[i]) cout << x << " ";
		cout << endl; 
	}*/
	
	f[2][1] = -a[1];
	if(len == 1) f[2][1] = 0;
	for(int i = 1; i < n; i++) {
		for(auto s : z[i]) {
			//if(i == 1) cout << "look : " << s << endl;
			for(int x = 1; x <= k; x++) {
				if(S[s][x]) {
					//if(i == 1) cout << "ppp : " << x << endl;
					int j = S[s][x]; //第i个数加入的是第x个集合 
					if(f[s][j] == 1e18) continue;
					
					//printf("f[%lld][%lld] = %lld\n", s, j, f[s][j]);
					
					//考虑填入a[i+1]
					for(int y = 1; y <= k; y++) { //将a[i+1]放入第y个集合里 
						if(a[i] == a[i + 1] && S[s][y] >= j) break;
						for(int h = 1; h <= k; h++) now[h] = S[s][h];
						now[y]++;
						if(now[y] > len) continue;
						int J = now[y], derta = 0;
						if(J == len) derta += a[i + 1];
						if(J == 1) derta -= a[i + 1];
						sort(now + 1, now + k + 1);
						int num = 0;
						for(int h = 1; h <= k; h++) 
							num = num * base + now[h];
						int Nxt_S = id[num];
						upd(f[Nxt_S][J], f[s][j] + derta);	
					}
					
				}	
				
			}
		}
	}
	
	if(f[tot][len] == 1e18) cout << -1;
	else cout << f[tot][len];
	return 0;
}

/*
6 3
1 1 1 1 2 5
*/