题目链接： https://vjudge.net/problem/FZU-2218
题意：给出一个字符串，求出它的两个子串，满足互相之间不含有相同字符，且长度的乘积最大，输出这个最大乘积。
分析：首先，我们要计算出这个字符串的所有子串包含的字符情况，因为不同字符的个数最多为16，所以我们可以通过一个长度为16的二进制串来表示某一个子串的字符包含情况，可以在 O(len(str)2) 的时间内统计出每一种字符包含情况下的最长子串长度，很多人在这个时候就急着遍历一遍所有情况求最大乘积了。其实并没有完：我们考虑并不是包含的字符数越多，子串的长度就越长，所以对于一个给定的字符包含情况，可能它的子集所对应的子串的长度更长，而它的子集肯定也能和它的对应集合相乘。所以我们应该从包含1个字符的情况往后退，每次将当前情况的最长长度和减少一个字符的子集的最长长度比较，最后推出每种情况下的最长长度。这个时候，我们才可以枚举所有情况，求最大乘积。
AC 代码：
/************************************************************************* > File Name: test.cpp > Author: Akira > Mail: qaq.febr2.qaq@gmail.com ************************************************************************/ #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <algorithm> #include <bitset> #include <queue> #include <stack> #include <map> #include <cmath> #include <vector> #include <set> #include <list> #include <ctime> #include <climits> typedef long long LL; typedef unsigned long long ULL; typedef long double LD; #define MST(a,b) memset(a,b,sizeof(a)) #define CLR(a) MST(a,0) #define Sqr(a) ((a)*(a)) using namespace std; #define MaxN 100001 #define MaxM MaxN*10 #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 const int mod = 1E9+7; const double eps = 1e-6; #define bug cout<<88888888<<endl; #define debug(x) cout << #x" = " << x << endl; int T,n,k; char str[2024]; int len[1<<20]; void solve() { CLR(len); for(int i=0;i<n;i++) { int state = 0; for(int j=i;j<n;j++) { int loc = str[j]-'a'; state |= (1<<loc); len[state] = max(len[state], j-i+1); } } for(int i=0;i<(1<<k);i++) { for(int j=0;j<k;j++) { if(i & (1<<j) ) { int sons = i-(1<<j); len[i] = max(len[i], len[sons]); } } } int ans = 0; for(int i=0;i<(1<<k);i++) { ans = max(ans, len[i]*len[ ((1<<k)-1)^i]); } printf("%d\n", ans); } int main() { //std::ios::sync_with_stdio(false); scanf("%d", &T); while(T--) { scanf("%d%d", &n, &k); scanf("%s", str); solve(); } //system("pause"); }