Problem Codeforces #541 (Div2) - E. String Multiplication
Time Limit: 2000 mSec
Problem Description
Input
Output
Print exactly one integer — the beauty of the product of the strings.
Sample Input
3
a
b
a
Sample Output
3
题解：这个题的思维难度其实不大，需要维护什么东西很容易想到，或者说套路十分明显
1、字符串无限制条件下最大值
2、强制选择左端点/右端点的最大值
3、是否只有一种字符
基本上需要维护的量就是这些，不过写起来实在是非常麻烦，以我的代码能力短时间实在是写不出来，后来参考了一位大佬的代码，写的思路清晰，代码简洁，实在是非常值得学习，之所以能够使得代码变简洁，主要是因为他枚举了字母。题目明确说明只有小写英文字母，所以最后的最大值无非就是这26个字母中的一个形成的，因此分别计算各个字母对应的最大值即可算出最终最大值，而一旦固定了每次考虑取最大值的字母，写代码的难度会大大降低，关键点就这一条，直接上代码。
#include <bits/stdc++.h> using namespace std; #define REP(i, n) for (int i = 1; i <= (n); i++)
#define sqr(x) ((x) * (x)) const int maxn = + ;
const int maxm = + ;
const int maxs = + ; typedef long long LL;
typedef pair<int, int> pii;
typedef pair<double, double> pdd; const LL unit = 1LL;
const int INF = 0x3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const double inf = 1e15;
const double pi = acos(-1.0); int n;
int len[maxn];
string str[maxn]; int main()
{
ios::sync_with_stdio(false);
cin.tie();
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n;
for (int i = ; i <= n; i++)
{
cin >> str[i];
len[i] = str[i].size();
}
int ans = ;
for (int c = ; c < ; c++)
{
int mx = , cnt = ;
for (int i = ; i < len[]; i++)
{
if (str[][i] - 'a' != c)
{
mx = max(mx, cnt);
cnt = ;
}
else
{
cnt++;
}
}
mx = max(mx, cnt);
for (int i = ; i <= n; i++)
{
int lmx = , rmx = ;
int nmx = ;
for (int j = ; j < len[i]; j++)
{
if (str[i][j] - 'a' == c)
lmx++;
else
break;
}
for (int j = len[i] - ; j >= ; j--)
{
if (str[i][j] - 'a' == c)
rmx++;
else
break;
}
cnt = ;
for (int j = ; j < len[i]; j++)
{
if (str[i][j] - 'a' != c)
{
nmx = max(nmx, cnt);
cnt = ;
}
else
cnt++;
}
nmx = max(nmx, cnt); if (nmx == len[i])
{
mx = (mx + ) * nmx + mx;
}
else
{
if (mx != )
mx = lmx + rmx + ;
else
mx = max(lmx, rmx);
}
mx = max(mx, nmx);
}
ans = max(ans, mx);
}
cout << ans << endl;
return ;
}