题目大意:
你有$k$个数,分为$26$种
对于每个数,你可以选择选进$A$集合或者$B$集合或者不选
要求$A$集合中必须有$n$个数,$B$集合中必须有$m$个数
记第$i$种数在$A$集合中的个数为$a_i$,$B$中个数为$b_i$
试最小代价$\sum a_i * b_i$
$k \leqslant 200000$,$n, m \leqslant 30000$
首先,我们打表得出一个结论,代价一定只由一种数得出
考虑证明:
我们不妨设代价由$A$得出,且集合$S_A$和$S_B$中分别有$i$个$A$和$a - i$个$A$
那么,如果我们尝试用$B$来替换$A$,不妨设从$B$中抽了$j$个$B$扔进$A$中,且一共有$b$个$B$
那么贡献差为$i * (a - i) - ((i - j) * (a - i + j) + j * (b - j))(0 \leq j \leq min(i, b))$
化简后,为$2j^2 - j(2i - a+ b)$
这是一个开口向上的,以$j$为自变量的二次函数
最大值一定在端点取到,也就是$j = 0$或者$j = i$或者$j = b$取到
这三种情况对应着代价由$A$得出或者由$B$得出
我们可以枚举在中间的种类是哪一个
之后再枚举放在$A$中的数能取多少个
相应地我们可以知道最多可以放在$B$中多少个
可以通过背包来实现上述问题
由于实现不优,复杂度为$O(26^2 * (n+ m) + 26 * k)$
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
namespace remoon {
#define ri register int
#define tpr template <typename ra>
#define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++)
#define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --)
#define gc getchar
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
int wr[], rw;
#define pc(iw) putchar(iw)
tpr inline void write(ra o, char c = '\n') {
if(!o) pc('');
if(o < ) o = -o, pc('-');
while(o) wr[++ rw] = o % , o /= ;
while(rw) pc(wr[rw --] + '');
pc(c);
}
}
using namespace std;
using namespace remoon;
#define sid 30050
#define kid 200050 char s[kid];
bool f[kid];
int n, m, k, t, cnt[]; inline int judge() {
f[] = ;
memset(f, , sizeof(f));
rep(i, , ) drep(j, k, cnt[i])
f[j] |= f[j - cnt[i]];
rep(i, n, k - m)
if(f[i]) { puts(""); return ; }
return ;
} inline void solve() {
int ans = 1e9;
rep(i, , ) {
memset(f, , (n + m) << );
f[] = ;
rep(j, , ) if(i != j)
drep(v, n + m, cnt[j]) f[v] |= f[v - cnt[j]]; rep(j, , n + m)
if(f[j]) {
int l = max(n - j, );
int r = max(m - (k - cnt[i] - j), );
if(l + r <= cnt[i]) ans = min(ans, l * r);
}
}
write(ans);
} int main() {
t = read();
while(t --) {
n = read(); m = read(); k = read();
scanf("%s", s + );
int sn = strlen(s + );
memset(cnt, , sizeof(cnt));
rep(i, , sn) ++ cnt[s[i] - 'A'];
if(judge()) continue;
solve();
}
return ;
}