题目链接：https://codeforc.es/contest/1070/problem/J
题意：给出一个长度为 k 的字符串，选出 n 个和 m 个不同位置的字符构成两个字符串，使得两个字符串相同字母的对数最少。
题解：在最优解的情况下，两个字符串相同的字母只有一个（假设有两种相同的字母，调换他们的位置变得只有一种相同字母的时候更优，可以自行草稿纸上写下不等式证明），可以枚举相同的字母，剩下的字母做 01 背包判断可以构成的最大长度即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 #define mst(a,b) memset((a),(b),sizeof(a)) 6 #define mp(a,b) make_pair(a,b) 7 #define pi acos(-1) 8 #define pii pair<int,int> 9 #define pb push_back 10 const int INF = 0x3f3f3f3f; 11 const double eps = 1e-6; 12 const int MAXN = 2e5 + 10; 13 const int MAXM = 1e3 + 10; 14 const ll mod = 1e9 + 7; 15 16 char s[MAXN]; 17 int cnt[30], dp[MAXN]; 18 19 int main() { 20 #ifdef local 21 freopen("data.txt", "r", stdin); 22 #endif 23 int t; 24 scanf("%d",&t); 25 while(t--) { 26 int n,m,k; 27 scanf("%d%d%d",&n,&m,&k); 28 scanf("%s",s + 1); 29 mst(cnt, 0); 30 for(int i = 1; i <= k; i++) cnt[s[i] - 'A' + 1]++; 31 ll ans = 1ll * n * m; 32 for(int i = 1; i <= 26; i++) { 33 for(int j = 1; j <= k; j++) dp[j] = 0; 34 dp[0] = 1; 35 for(int j = 1; j <= 26; j++) { 36 if(i == j) continue; 37 for(int h = k; h >= cnt[j]; h--) dp[h] |= dp[h - cnt[j]]; 38 } 39 for(int j = 0; j <= k; j++) { 40 if(!dp[j]) continue; 41 int x = max(0, n - j), y = max(0, m - (k - cnt[i] - j)); 42 if(x + y <= cnt[i]) ans = min(ans, 1ll * x * y); 43 } 44 } 45 printf("%lld ",ans); 46 } 47 return 0; 48 }