题目大意：给一个长度为n由k种字母组成的字符串，求其中两个子串，要求它们不包含相同的字母且长度的乘积最大。
子集的枚举问题，状态压缩，设d[i]为状态为i时所代表的集合的子集字母所能构成的最大长度，为什么不是相应代表的集合呢？因为，它的子集完全可以有可能构成比它还要长的长度，如果在最后计算时再算各个状态的子集，复杂度难以承受，所以我们在一开始求出d[i]严格拥有i状态后，再递推一次，转移就是，dp[i] = max(dp[i], dp[i ^ (1 << j)])，i拥有第j个元素。最后枚举状态，求相应的补集更新最大值即可。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int const CON = 16; int dp[(1 << CON) + 5]; char s[2005]; int main() { int T; scanf("%d", &T); while(T --) { memset(dp, 0, sizeof(dp)); int n, k, sta, tot; scanf("%d %d", &n, &k); scanf("%s", s); tot = 1 << k; for(int i = 0; i < n; i++) { sta = 0; for(int j = i; j < n; j++) { sta |= (1 << (s[j] - 'a')); dp[sta] = max(dp[sta], j - i + 1); } } for(int i = 0; i < tot; i++) { for(int j = 0; j < k; j++) { if(i & (1 << j)) { dp[i] = max(dp[i], dp[i - (1 << j)]); } } } int ans = 0; for(int i = 0; i < tot; i++) { ans = max(ans, dp[i] * dp[(tot - 1) ^ i]); } printf("%d\n", ans); } }